logo search
discrete_math1

1. Основные понятия теории графов, удаленность вершины, центр, радиус и диаметр графа.

Графом Gназывается пара (V,E), где– непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Пусть ребро е соединяет вершины uиv. В этом случае пишутe= [u,v] и говорят, что

  • uиvявляются концами ребра е;

  • вершины uиvсмежны;

  • вершины uиvинцидентны ребру е, ребро е инцидентно вершинамuиv.

Определение. Степенью вершины называется количество инци­дентных ей ребер.

Определение. Вершина называется изолированной, если она не инцидентна ни одному ребру; вершина называется концевой, если ей инцидентно только одно ребро.

Рис.1

Утверждение. Если в графе количество вершинn≥ 2, то в нем найдутся хотя бы две вершины с одинаковой степенью.

Утверждение. Для любого графаG= (V,E) сnвершинами иmребрами справедливо равенство т.е. сумма степеней всех вершин графа равна удвоенному количеству ребер.

Определение. Последовательность ребер, в которой все ребра различны, называется цепью длиныk, соединяющей вершиныи. При этом вершиныиназываются концами цепи.

Определение. Расстоянием между вершинамиuиvназывается число, равное длине кратчайшей цепи, соединяющей вершиныuиv.

Определение. Эксцентриситетом вершиныuназывается число, равное максимальному расстоянию от вершиныuдо остальных вершин графа, т.е..

Определение. Радиусом графаGназывается числоr(G), равное минимальному эксцентриситету его вершин, т.е..

Определение. Диаметром графаGназывается числоd(G), равное максимальному эксцентриситету его вершин, т.е..

Известно, что для любого графа Gвыполняется соотношение.

Определение. Центром графаGназывается множество его вершин, имеющих минимальный эксцентриситет.

Пример 2. Рассмотрим графG, изображенный на рис.2. Эксцентриситеты его вершин:

.

Следовательно, его радиус и диаметр r(G) = 2,d(G) = 4, а центр – вершина.

Рис.2