68. Связные компоненты графа.

Две вершины Vi и Vj называются связными в графе G, если в нем существует маршрут для которого Vi и Vj являются началом и концом.

Граф G назывется связным, если каждая пара его вершин явл. связной, иначе граф называется не связным.

Если вершина V графа G связана с какой-либо другой вершиной, то она связана сама с собой.

Отношение связности 2-х вершин, заданное на множестве обладает свойствами рефлексивности, симметричности и транзитивности. Проверить или показать, каким образом отношение связности является отношением эквивалентности. Следовательно определяет разбиение мн. вершин графа на непересекающиеся подмножества.

Вершины одного и того же множества связаны между собой, а вершины различных мн. – не связаны, поэтому в графе G нет ребра, которое бы имело концы в вершинах из разных множеств.

69. Расстояния в графе.

Пусть G – неориентированный граф, v и v - любые две его вершины. Тогда существует связывающая их простая цепь М (е₁,е₂,…, е_q). Если количество q ребер этой цепи – не минимальное из возможных, то существует цепь М (е₁,е₂,…, е_q), связывающая v и v и имеющая меньшее число ребер. Если М не минимально, то можно найти связывающую v и v цепь с еще меньшим количеством ребер и тд. Однако этот процесс уменьшения числа ребер можно повторить не более q раз, так как это число каждый раз уменьшается не меньше ем на единицу. Поэтому существует связывающая v и v цепь М^(е^₁,е^₂,…, е^_p) с минимальным количеством ребер р. Минимальная длина простой цепи с началом v и концом v называется расстоянием d(v,v) между этими вершинами.

Считая каждую вершину v неориентированного графа связной с самой собой, мы по существу ввели нулевые маршруты, не содержащие ребер, с началом и концом в любой вершине vG. В соответствии с этим расстояние d (v,v) между вершиной v и ею самою равно 0. Для любой пары v,vG различных вершин d(v,v)>0, т.к. связывающая эти вершины цепь состоит хотя бы из одного ребра.

Расстояние d(v,v) удовлетворяет аксиомам метрики:

1) d(v,v)0, причем d(v,v)=0, когда v=v;

2) d(v,v)= d(v,v);

3) справедливо неравенство треугольника: d(v,v)+d(v,v)d(v,v).

В особом доказательстве нуждается только последнее свойство. Пусть M (v,v) и М (v,v) – минимальные простые цепи, связывающие v с v и v с v. Тогда последовательность ребер М, в которой сначала идут все ребра цепи M, а затем ребра цепи M, - это маршрут, связывающий v и v и имеющий длину d(v,v)+d(v,v). Как показано ранее, если этот маршрут не является простой цепью, то можно найти более короткую цепь М^, связывающую v и v. Поэтому во всяком случае минимальная связывающая эти вершины цепь имеет длину, не превосходящую d(v,v)+d(v,v).

70. Диаметр, радиус, центр графа.

Пусть G – конечный неориентированный граф. Тогда можно определить его диаметр d(G)=max d(v,v). Кратчайшие простые цепи, связывающие вершины v,vG с максимальным расстоянием между ними, называются диаметральными простыми цепями.

Пусть v – произвольная вершина рассматриваемого графа G. Максимальным удалением в графе G от вершины v называется величина r(v)=max d(v,v). Вершина v называется центром графа G, если максимальное удаление от нее принимает минимальное значение r(G)=min r(v). Максимальное удаление r(G) от центра называется радиусом графа, а любая кратчайшая цепь от центра v до максимально удаленной от него вершины v - радиальной цепью.

Центр не обязательно должен быть единственным. Например, в полном неориентированном графе K(V), в котором любые две различные вершины v,vV соединены ребром, радиус равен единице и любая вершина vV является центром.