Основы теории графов (раздел дискретной математики, изучающий свойства графов)
1. Основные понятия теории графов
1.1. Граф
1.1.1. Если на плоскости задать конечное множество V точек и конечный набор линии E, соединяющий некоторые пар точек, то полученная совокупность точек и линии называется графом.
1.2. Ребро
1.2.1. линия, соединяющая пару смежных вершин графа
1.3. Вершина
1.3.1. элемент (точка) графа, обозначающий объект любой природы, входящий в множество объектов, описываемое графом.
1.4. Инцидентность
1.4.1. Инцидентность вершины и ребра - это, если вершина является началом или концом ребра. Если ребро графа соединяет две вершины, то это ребро им инцидентно. Две вершины (или два ребра) инцидентными быть не могут.
1.4.1.1. Вершина 1 инцидентна ребру 1-2
1.5. Смежность
1.5.1. Смежность – понятие, используемое в отношении только двух рёбер, либо только двух вершин: два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
1.5.1.1. Вершина 1 и 2 смежные, так как инцидентны одному ребру
1.6. Маршрут
1.6.1. Маршрут - это проход по графу через заданную последовательность вершин.
1.6.1.1. Открытый маршрут: вершины 2-4-1-2-3-4-1
1.6.1.2. Замкнутый маршрут: вершины 2-3-5-4-3-2
1.7. Петля
1.7.1. Если ребро соединяет одну и ту же вершину, то она называется петлей.
1.7.1.1. Граф с петлей (вершина 4)
2. Виды графов
2.1. Направленный (ориентированный)
2.1.1. Направленные (ориентированные) - это граф, на всех ребрах которого выбрано одно из двух направлений. Ребра в ориентированном графе часто называют дугами
2.2. Ненаправленный (неориентированный)
2.2.1. Ненаправленные (неориентированные) - это такое граф, в котором можно двигаться в обе стороны от вершины к вершине
2.3. Взвешенный граф
2.3.1. Взвешенный граф - это граф, в котором каждому ребру в соответствие поставлено некоторое числовое значение – вес
2.4. Невзвешенный граф
2.4.1. Невзвешенный граф - это граф, в котором не поставлено никакое числовое значение ребрам
2.5. Смешанный граф
2.5.1. Граф, в котором присутствуют как ориентированные ребра, так и неориентированные, называется смешанным
2.6. Связный (рис.8) и несвязный (рис.7) графы
2.6.1. Граф называется связным, если любые две его вершины могут быть соединены путем, т. е. последовательностью ребер, каждое следующее из которых начинается в конце предыдущего. Граф называется несвязным, если это условие не выполняется.
2.7. Цикл Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.9а). В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5.
2.7.1. Циклом называется путь, в котором совпадают начало с концом.
3. Формы представления графа
3.1. Матрица инцидентности
3.1.1. Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам.
3.2. Матрица смежности
3.2.1. Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.
3.3. Таблица ребер графа
3.3.1. Таблица ребер состоит из двух столбцов: в левом - название ребер, а в правом - инцидентные этому ребру вершины. Для ориентированных графов обязательно сначала указывается начало ребра, затем конец.
4. Изоморфизм графа
4.1. Графы называют изоморфными, если они могут существовать в разных формах, имеющих одинаковое количество вершин, ребер, а также одинаковую связность ребер. Два графа G1 и G2 называются изоморфными, если: 1. Их количество компонентов (вершин и ребер) одинаково. 2. Их пограничное соединение сохраняется.
4.1.1. Граф G
4.1.2. Граф Н
4.1.3. Изоморфизм между графами G и H: a-1 b-6 c-8 d-3 g-5 h-2 i-4 j-7