Федоров В.Н. - Введение в теорию графов (1023556), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Таким образом, в каждом конкретном случае следует уточнять, какой именно вариант определения используется.

1. Матрица инцидентности графа (incidence matrix) G=(V, E) – прямоугольная матрица S=||s_ij||, размерностью n m. s_ij=1, тогда и только тогда, когда вершина x_i инцидентна ребру r_j в графе G и s_ij=0 в противном случае.

Для орграфа учитывается ориентация:

s_ij =

Каждый столбец содержит один элемент, равный +1, и один элемент, равный –1, либо константу.

1. Матрица расстояний (кратчайших цепей) графа (reachability matrix) G – квадратная матрица D=||d_ij||, в которой элемент d_ij= (x_i, x_j), т.е. численно равен расстоянию от вершины x_i до вершины x_j в графе G. Если из x_i недостижима вершина x_j, то d_ij=.

2. Матрица достижимости орграфа G – квадратная матрица R=||r_ij||, в которой элемент r_ij=1, если из вершины x_i достижима вершина x_j в орграфе G.

3. Массив степеней вершин – матрица строка, i–й элемент которой равен степени вершины x_i графа G.

4. Массив полустепени (степени (исхода) захода) вершин – матрица строка, i–й элемент которой равен полустепени исхода (захода) вершины x_i орграфа.

5. Массив ребер (дуг) – пара массивов IE(m), OE(m), задающих орграф G=(V, E), m=|E|. Дуга u_k=(x_i, x_j), u_kE, если IE(k)=i, OE(k)=j. Ребро графа задается парой противоположно ориентированных дуг.

6. Массив предшественников (для деревьев) – PR(l). В вершину с номером i входит дуга из вершины j – PR(i) = j, l – число вершин.

7. Окрестность вершины – для графа G=(V, E) окрестностью вершины xV называется множество O(x) всех вершин, смежных с х. Для орграфа окрестностями O^–(x) и O⁺(x) будет множество всех вершин таких, что yO^–(x), если (y, x)E, и yO⁺(x), если (x, y)E.

8. Число вершинной связности графа G – наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.

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

10. Обхват графа – длина его минимального цикла.

11. Окружение графа – длина его самого длинного простого цикла.

12. Радиус графа (radius) – наименьший из эксцентриситетов его вершин.

13. Диаметр графа (diameter) – максимальный эксцентриситет его вершин.

14. Средний диаметр – сумма кратчайших расстояний между всеми парами вершин графа, деленная на число пар вершин.

15. Цикломатическое число или ранг неориентированного графа G=(V, E) есть (G)=|E| – |V| + (G), где (G) – число компонент связности графа G. (По другому (G)=m – n + (G).)

16. Хроматическое число (chromatic number) (G) – наименьшее число p, для которого граф G имеет p–раскраску.

17. Хроматический класс '(G) – наименьшее число p, для которого существует реберная p–раскраска.

18. Кликовое число (плотность) (clique number) – максимальный по числу вершин размер клики в графе G.

19. Число вершинной независимости (число внутренней устойчивости, неплотность графа) (G) – наибольшее число вершин в независимых множествах вершин графа G.

20. Доминирующее число (число внешней устойчивости) (G)– наименьшее число вершин в доминирующем множестве.

21. Число вершинного покрытия (опора) – наименьшее число вершин в вершинном покрытии.

22. Число реберного покрытия – наименьшее число ребер в реберном покрытии графа.

23. Число планарности графа – наименьшее число ребер графа, удаление которых превращает граф в планарный граф.

24. Толщина графа – наименьшее число плоскостей, на которых граф размещается без пересечения ребер (обозначается t(G)).

25. Изоморфизм графов. Два графа G=(V, E) и L=(V', E') изоморфны (эквивалентны), если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохраняющие смежность и ориентацию для дуг.

26. Автоморфизм графа (automorphism) – изоморфизм графа G на себя.

27. Изоморфное вложение (изоморфизм подграфов). Граф G₂ изоморфно вложим в граф G₁, если в графе G₁ существует подграф, изоморфный графу G₂.

28. Гомеоморфизм графов. Два графа G₁ и G₂ гомеоморфны, если у них существуют изоморфные подразделения ребер и вершин.

29. Раскраска [вершинная] (colouring) – приписывание цветов (натуральных чисел) вершинам графа, такое, что никакие две смежные вершины не получают одинаковые цвета (числа).

30. Раскраска реберная (edge–colouring) – приписывание цветов ребрам графа, такое, что никакие два смежных ребра не получают одинакового цвета.

31. Раскраска точная – раскраска с использованием минимального числа красок, т. е. число красок равно хроматическому числу графа G или хроматическому классу графа G.

32. Раскраска приближенная – раскраска с использованием красок, количество которых больше или равно минимально возможному числу.

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

34. Объединение графов (помеченных графов) G₁=(V₁, E₁) и G₂=(V₂, E₂) – граф G₁G₂, множеством вершин которого является V=V₁V₂, а множеством ребер E=E₁E₂.

35. Пересечение графов (помеченных графов) G₁=(V₁, E₁) и G₂=(V₂, E₂) – граф G₁G₂, множеством вершин которого является V=V₁V₂, а множеством ребер E=E₁E₂ .

36. Соединение (сумма) графов G₁=(V₁, E₁) и G₂=(V₂, E₂) таких, что V₁V₂=, E₁E₂=– граф G₁+G₂, который состоит из G₁G₂K(V₁, V₂), где K(V₁, V₂) – полный двудольный граф с множеством вершин V₁ и V₂ в долях.

37. Произведение графов G₁=(V₁, E₁) и G₂=(V₂, E₂) – граф G₁G₂, состоящий из множества вершин V=V₁V₂, в котором две вершины s=(x₁, x₂) и t=(y₁, y₂) (s, t  V, x₁, y₁  V₁, x₂, y₂  V₂) смежны тогда и только тогда, когда x₁=y₁ и x₂ смежна с y₂ или x₂=y₂ и x₁ смежна с y₁.

38. Разность графов (помеченных графов) – граф G₁\G₂, который получается из G₁ удалением элементов, соответствующих графу G₂.

39. Симметрическая (кольцевая) сумма графов

G₁(V₁,E₁) и G₂(V₂,E₂) – граф G(V,E) = G₁G₂ = G₁G₂\G₁G₂ =

1. Композиция графов (лексикографическое произведение графов) G₁=(V₁, E₁) и G₂=(V₂, E₂) – граф G=G₁[G₂], состоящий из множества вершин V=V₁V₂, и две вершины s=(x₁, x₂) и t=(y₁, y₂) (s, t  V, x₁, y₁  V₁, x₂, y₂  V₂) смежны в G тогда и только тогда, когда x₁ смежна с y₁ или x₁=y₁ и x₂ смежна с y₂.

3. Части графов

1. Подграф графа (subgraph) G=(V, E) – граф G'=(V', E'), для которого V'V, E'E и две несмежные вершины в G не смежны в G'.

2. Часть графа (section graph) G=(V, E) – граф G'=(V', E'), для которого V'V, E' E и не всегда две смежные вершины в G смежны в G'.

3. Суграф (остовный подграф) графа G=(V, E) – граф G'= (V, E'), который содержит то же множество вершин, что и сам граф G и E'E.

4. Остов графа (остовное дерево, покрывающее дерево, каркас) (spanning tree) – суграф графа G, не содержащий циклов и имеющий столько же компонент связности, что и G.

5. Компонента связности графа (connected component) – максимальный подграф, возможно не единственный, графа G, в котором все вершины попарно достижимы.

6. Сильная компонента орграфа G – максимальный подграф орграфа G, в котором любая пара вершин сильно связна.

7. Полный подграф (complete subgraph) – подграф, в котором каждая пара вершин смежна.

8. Клика (clique) – полный подграф графа G, такой, что в G не существует вершины, смежной со всеми вершинами данного подграфа (т.е. это максимальный полный подграф).

9. Треугольник графа – полный подграф, состоящий из трех вершин.

10. Односторонняя компонента орграфа – максимальный подграф, для любых двух вершин которого, по крайней мере, одна достижима из другой.

11. Слабая компонента орграфа – максимальный слабый подграф графа.

12. Маршрут (chain, walk) – чередующаяся последовательность x₁, u₁, x₂, u₂, ... , x_k вершин x_i и ребер u_i, обладающая тем свойством, что любая пара соседних элементов инцидентна.

13. Цепь (trail, path) – маршрут, в котором все ребра различны.

14. Простая цепь [простой путь] (elementary path) – цепь, в которой все вершины различны.

15. Цикл (cycle) – цепь, у которой начальная и конечная вершины совпадают.

16. Простой цикл – простая цепь, у которой концевые вершины совпадают.

17. Ориентированная цепь – цепь орграфа G, в которой ориентация дуг совпадает (обычно называют просто путь).

18. Контур (elementary circuit) – ориентированная цепь, у которой начальная и конечная вершины совпадают.

19. Грань плоского графа – область плоскости, ограниченная ребрами связного плоского графа и не содержащая внутри себя ни ребер, ни вершин.

20. Эйлерова цепь (Euler path) – цепь, содержащая все ребра графа в точности один раз.

21. Эйлеров цикл (Euler_cycle) – эйлерова цепь, у которой начальная и конечная вершины совпадают.

22. Гамильтонова цепь (Hamilton path) – простая цепь, которая содержит все вершины графа.

23. Гамильтонов цикл (Hamilton cycle) – гамильтонова цепь, у которой начальная и конечная вершины совпадают.

24. Независимые (вершинно–непересекающиеся, вершинно–независимые) маршруты – множество маршрутов, у которых все элементы различны (быть может, кроме конечных вершин).

25. Реберно–независимые (реберно–непересекающиеся) маршруты – множество маршрутов, у которых ребра (дуги) различны, т.е. не существует ребра, которое одновременно принадлежит нескольким маршрутам.

26. (s, t)–цепь (путь) ((s, t)–path) – цепь, у которой вершины s и t концевые.

27. Дополняющая цепь – ненасыщенная (s, t)–цепь (путь), позволяющая увеличить поток в сети.

28. Разрез (сечение графа) (cut–set) – множество элементов, удаление которых увеличивает число компонент (односторонних компонент, слабых компонент) связности графа.

29. Простой разрез – разрез, у которого любое собственное подмножество элементов не является разрезом.

30. Смешанный разрез – разрез, элементами которого выступают как ребра (дуги), так и вершины.

31. Реберный разрез – все элементы разреза ребра (дуги).

32. Вершинный разрез. Все элементы разреза – вершины.

33. (s, t)–разрез – разрез, из–за удаления которого вершина t не достижима из s.

34. Независимое множество элементов (упаковка) [независимое множество вершин или ребер] (independent vertex or link set) – множество ребер (дуг) или вершин, попарно несмежных.

35. Вершинное покрытие (опора) – множество V' вершин, таких, что всякое ребро инцидентно вершине из V'.

36. Реберное покрытие (покрывающий суграф) [доминирующее множество ребер] (edge covering) – множество E' ребер, таких, что всякая вершина инцидентна ребру из E'.

37. Минимальное покрытие – минимально возможное число элементов в соответствующем покрытии.

38. Независимое множество вершин (внутренне устойчивое множество, пустой подграф) (independent vertex set) – множество V' вершин, в котором никакие две вершины не смежны.

39. Максимальное независимое множество вершин (maximal independent vertex set) – такое независимое множество вершин, что при добавлении в него любой другой вершины графа это множество перестает быть независимым.

Примечание: "максимальность" в смысле данного определения означает не максимальную мощность, а "нерасширяемость" множества; в общем случае граф может иметь несколько максимальных независимых множеств вершин разной мощности.

1. Паросочетание (независимое множество ребер) (matching, independent link set) – множество E' ребер двудольного графа, в котором никакие два ребра не смежны.

2. Совершенное паросочетание (perfect matching) – такое паросочетание, что любая вершина графа инцидентна некоторому ребру этого паросочетания.

3. Доминирующее множество вершин (внешне устойчивое множество) – множество V' вершин, таких, что каждая вершина, не принадлежащая V', смежна с вершиной из V'.

4. Минимальный разрез – разрез с наименьшим числом элементов или с минимальной пропускной способностью.

5. Минимальная цепь – (s, t)–цепь с минимальным числом ребер.

6. Максимальный разрез – разрез с наибольшим числом элементов среди всех простых разрезов графа.

7. Максимальная цепь – простая (s, t)–цепь с максимально возможным числом ребер.

8. Максимальная клика – клика с максимально возможным числом вершин среди клик графа.

9. Максимальное паросочетание – паросочетание с максимально возможным числом ребер в паросочетании данного графа (числом реберной независимости).

10. Фундаментальный цикл (контур) – цикл, определяемый некоторым остовом и хордой графа (орграфа). Точнее: Фундаментальным циклом графа G=(V,E) с остовным деревом T=(V,E') называется простой цикл, получаемый в результате добавления в T одного из ребер G, не принадлежащего E'. Количество фундаментальных циклов графа G=(V,E) при любом фиксированном остовном дереве T=(V,E') равно цикломатическому числу G.

11. Фундаментальный разрез – разрез G=(V,E) относительно ветви b_i остова T, состоящий из множества ребер {b_i, h_i1, …, h_ij} – это разрез графа, содержащий точно одну ветвь остова графа Т. Количество фундаментальных разрезов графа G=(V,E) при любом фиксированном остовном дереве T=(V,E') называется корангом графа и равно v*=n–1.

12. Минимальный цикл (обхват) – цикл с минимально возможным числом ребер среди всех циклов графа.

13. Расстояние между вершинами s и t – равно длине минимальной (s, t)–цепи.

14. Взвешенный граф – граф, вершинам и/или (обычно) ребрам которого поставлены в соответствие целые или вещественные числа (веса).

15. Вес (длина) – число, поставленное в соответствие взвешенному элементу графа.

16. Величина (разреза, цепи, цикла и т. п.) – суммарный вес элементов, входящих в данное подмножество.

17. Поток в сети – функция, сопоставляющая каждой дуге e = (i, j) неотрицательное вещественное число f(e) = f(i, j) так, что удовлетворяются следующие условия:

1. f(i, j) 0

Характеристики

Список файлов книги