Тема лекции: Метрические характеристики графов

 

В теории графов применяются:

 

1. Матрица инцинденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими рёбрам. Для ориентированного графа столбец, соответствующий дуге (х,y) содержит -1 в строке, соответствующей вершине х и 1 в строке, соответствующей вершине у. Во всех остальных – 0. Петлю, т. е. дугу (х,х) можно представлять иным значением в строке х, например, 2. Если граф неориентированный, то столбец, соответствующий ребру (х,у) содержит 1, соответствующие х и у – нули во всех остальных строках.

 

2. Матрица смежности. Это матрица n*n где n – число вершин, где b_ij = 1, если существует ребро, идущее из вершины х в вершину у и b_ij = 0 в противном случае.

 

3. Пусть G=(X,U) - связный граф, а  - две его несовпадающие вершины. Длина кратчайшего маршрута, соединяющего вершины  (пути из ) называется расстоянием между вершинами  и обозначается . Положим , если вершины  не соединены маршрутом (путем). Расстояние  удовлетворяет следующим аксиомам:

1) ;

2) ;

3)  тогда и только тогда, когда ;

4)  для симметрических графов;

5)  (неравенство треугольника).

 

4. Расстояние для графа G удобно задавать матрицей расстояний. Матрицей расстояний графа с n вершинами называется квадратная матрица D порядка n, элементы которой определяются следующим образом:

Матрицу расстояний можно определить

 

5. Для фиксированной вершины  величина

называется эксцентриситетом (отклоненностью) вершины .

 

6. Максимальный среди эксцентриситетов вершин называется диаметром графа G и обозначается diam (G):

7. Минимальный из эксцентриситетов вершин связного графа называется его радиусом и обозначается через r(G):

 

8. Вершина, имеющая минимальный эксцентриситет, называется центром графа.

9. Для вершины  число  называется передаточным числом.

10. Вершина графа, которой соответствует минимальное передаточное число

 

называется медианой графа. Центров и медиан в графе может быть несколько.

 

Рис. 1

 

Пример. Для графа, изображенного на рис.1 метрические характеристики определяются следующим образом:

 

Радиус графа равен 1, диаметр равен 2. Центр графа - вершина ; Медиана графа - вершина .

Контрольные вопросы:

1. Что такое граф?

2. Приведите разновидности графов.

3. Может ли пустой граф быть ориентированным?

4. Нарисуйте полный граф.

5. Что такое подграф?

6. Каким образом понятие дерева активно используется в информатике и программировании?

7. Метрические характеристики графов.

 

 

Тема 4.2.Остовы графов, деревья

 

Деревья

 

Определение: Деревом называют связный граф без циклов. Пример: Название достаточно жизненно - взгляните на рисунок:

 

Теорема: В любом дереве вершин ровно на одну больше, чем ребер.

Док-во: Будем доказывать этот факт индукцией по количеству вершин.

Когда вершин - две ясно, что ребро ровно одно, так что база индукции очевидна.

Переход: Возьмем любое дерево. В нем есть висячая вершина. Уберем ее вместе с ребром, которое к ней ведет. Оставшееся по-прежнему будет деревом, т.к. циклы появиться не могли, и связность нарушиться тоже не могла. Но тогда в остатке вершин на одну больше, чем ребер по предположению индукции, а значит и в исходном графе тоже, т.к. есть одна дополнительная вершина и одно ребро.

 

Теорема: В любом связном графе с n вершинами хотя бы n -1 ребро, причем если количество ребер ровно n -1, то это дерево.

Док-во: Пусть это не дерево (иначе ребер ровно n-1 по предыдущей теореме), значит, в нем есть цикл. Сотрем любое из ребер этого цикла - граф останется связным. Если в нем остался еще цикл, то сотрем ребро и из него, и т.д. Ясно, что граф все время остается связным, так что в конце получится связный граф без циклов - дерево - у него ровно n-1 ребро, а значит у исходного графа хотя бы п.

.                                                                                                                                         

Теорема: Следующие утверждения равносильны:  

Граф является деревом.