Графики и графические модели
В предыдущей части были представлены различные инструменты для рассуждений, проверки и решения проблем. В этой части мы изучим дискретные структуры, которые составляют основу для формулирования многих реальных проблем.
Две дискретные структуры, которые мы рассмотрим, - это графы и деревья. Граф - это набор точек, называемых узлами или вершинами, которые связаны между собой набором линий, называемых ребрами. Изучение графиков, илиgraph theory является важной частью ряда дисциплин в области математики, инженерии и информатики.
Что такое график?
Definition - Граф (обозначаемый как $ G = (V, E) $) состоит из непустого набора вершин или узлов V и набора ребер E.
Example - Допустим, График - это $ G = (V, E) $, где $ V = \ lbrace a, b, c, d \ rbrace $ и $ E = \ lbrace \ lbrace a, b \ rbrace, \ lbrace a , c \ rbrace, \ lbrace b, c \ rbrace, \ lbrace c, d \ rbrace \ rbrace $
Degree of a Vertex - Степень вершины V графа G (обозначается deg (V)) - это количество ребер, инцидентных вершине V.
| Вершина | Степень | Даже странно |
|---|---|---|
| а | 2 | четный |
| б | 2 | четный |
| c | 3 | странный |
| d | 1 | странный |
Even and Odd Vertex - Если степень вершины четная, вершина называется четной вершиной, а если степень вершины нечетная, вершина называется нечетной вершиной.
Degree of a Graph- Степень графа - это наибольшая степень вершины этого графа. Для приведенного выше графика степень графика равна 3.
The Handshaking Lemma - В графе сумма всех степеней всех вершин равна удвоенному количеству ребер.
Типы графиков
Существуют разные типы графиков, о которых мы узнаем в следующем разделе.
Нулевой график
Нулевой граф не имеет ребер. Нулевой граф из $ n $ вершин обозначается $ N_n $.
Простой график
Граф называется простым графом / строгим графом, если граф неориентированный и не содержит петель или кратных ребер.
Мульти-граф
Если в графе разрешено несколько ребер между одним и тем же набором вершин, он называется Мультиграфом. Другими словами, это граф, имеющий как минимум одну петлю или несколько ребер.
Направленный и неориентированный граф
Граф $ G = (V, E) $ называется ориентированным графом, если множество ребер состоит из упорядоченной пары вершин, и граф называется неориентированным, если множество ребер состоит из неупорядоченной пары вершин.
Связанный и отключенный график
Граф является связным, если любые две вершины графа соединены путем; в то время как граф несвязный, если хотя бы две вершины графа не соединены путем. Если граф G несвязен, то каждый максимальный связный подграф в $ G $ называется связной компонентой графа $ G $.
Регулярный график
Граф является правильным, если все вершины графа имеют одинаковую степень. В регулярном графе G степени $ r $ степень каждой вершины графа $ G $ равна r.
Полный график
Граф называется полным графом, если каждые две пары вершин соединены ровно одним ребром. Полный граф с n вершинами обозначается $ K_n $
График цикла
Если граф состоит из одного цикла, он называется графом циклов. Граф циклов с n вершинами обозначается $ C_n $
Двудольный граф
Если множество вершин графа G можно разбить на два непересекающихся множества, $ V_1 $ и $ V_2 $, таким образом, что каждое ребро в графе соединяет вершину в $ V_1 $ с вершиной в $ V_2 $, и в G нет ребер, соединяющих две вершины в $ V_1 $ или две вершины в $ V_2 $, то граф $ G $ называется двудольным графом.
Полный двудольный граф
Полный двудольный граф - это двудольный граф, в котором каждая вершина в первом наборе соединена с каждой отдельной вершиной во втором наборе. Полный двудольный граф обозначается $ K_ {x, y} $, где граф $ G $ содержит $ x $ вершин в первом наборе и $ y $ вершин во втором наборе.
Представление графиков
В основном есть два способа представить график:
- Матрица смежности
- Список смежности
Матрица смежности
Матрица смежности $ A [V] [V] $ - это двумерный массив размером $ V \ times V $, где $ V $ - количество вершин в неориентированном графе. Если есть ребро между $ V_x $ и $ V_y $, тогда значение $ A [V_x] [V_y] = 1 $ и $ A [V_y] [V_x] = 1 $, в противном случае значение будет равно нулю. А для ориентированного графа, если есть ребро между $ V_x $ и $ V_y $, тогда значение $ A [V_x] [V_y] = 1 $, в противном случае значение будет равно нулю.
Adjacency Matrix of an Undirected Graph
Давайте рассмотрим следующий неориентированный граф и построим матрицу смежности -
Матрица смежности указанного выше неориентированного графа будет -
a |
b |
c |
d |
|
a |
0 |
1 |
1 |
0 |
b |
1 |
0 |
1 |
0 |
c |
1 |
1 |
0 |
1 |
d |
0 |
0 |
1 |
0 |
Adjacency Matrix of a Directed Graph
Рассмотрим следующий ориентированный граф и построим его матрицу смежности -
Матрица смежности указанного выше ориентированного графа будет -
a |
b |
c |
d |
|
a |
0 |
1 |
1 |
0 |
b |
0 |
0 |
1 |
0 |
c |
0 |
0 |
0 |
1 |
d |
0 |
0 |
0 |
0 |
Список смежности
В списке смежности массив $ (A [V]) $ связанных списков используется для представления графа G с числом вершин $ V $. Запись $ A [V_x] $ представляет собой связанный список вершин, смежных с вершиной $ Vx-th $. Список смежности неориентированного графа показан на рисунке ниже -
Планарный и неплоский граф
Planar graph- Граф $ G $ называется планарным, если его можно нарисовать на плоскости без пересечения ребер. Если мы рисуем граф на плоскости без пересечения ребер, это называется вложением графа в плоскость.
Non-planar graph - Граф не является плоским, если его нельзя нарисовать на плоскости без пересечения ребер графа.
Изоморфизм
Если два графа G и H содержат одинаковое количество вершин, соединенных одинаковым образом, они называются изоморфными графами (обозначаются $ G \ cong H $).
Неизоморфизм проверить легче, чем изоморфизм. Если возникает какое-либо из этих следующих условий, то два графа неизоморфны:
- Количество подключаемых компонентов разное
- Мощность множества вершин различна
- Количество элементов Edge-set различно
- Последовательности степеней разные
пример
Следующие графики изоморфны -
Гомоморфизм
Гомоморфизмом графа $ G $ в граф $ H $ называется отображение (может не быть биективным) $ h: G \ rightarrow H $ такое, что - $ (x, y) \ in E (G) \ rightarrow (h (x), h (y)) \ в E (H) $. Он отображает смежные вершины графа $ G $ в смежные вершины графа $ H $.
Свойства гомоморфизмов
Гомоморфизм - это изоморфизм, если это биективное отображение.
Гомоморфизм всегда сохраняет ребра и связность графа.
Композиции гомоморфизмов также являются гомоморфизмами.
Выяснить, существует ли какой-либо гомоморфный граф другого графа, является NP-полной задачей.
Графы Эйлера
Связный граф $ G $ называется графом Эйлера, если существует замкнутый след, включающий каждое ребро графа $ G $. Путь Эйлера - это путь, который использует каждое ребро графа ровно один раз. Путь Эйлера начинается и заканчивается в разных вершинах.
Схема Эйлера - это схема, которая использует каждое ребро графа ровно один раз. Схема Эйлера всегда начинается и заканчивается в одной и той же вершине. Связный граф $ G $ является графом Эйлера тогда и только тогда, когда все вершины графа $ G $ имеют четную степень, а связный граф $ G $ является эйлеровым тогда и только тогда, когда его множество ребер можно разложить на циклы.
Приведенный выше график является графом Эйлера как $ «a \: 1 \: b \: 2 \: c \: 3 \: d \: 4 \: e \: 5 \: c \: 6 \: f \: 7 \: g ”$ покрывает все ребра графа.
Гамильтоновы графы
Связный граф $ G $ называется гамильтоновым графом, если существует цикл, включающий каждую вершину $ G $, и цикл называется гамильтоновым циклом. Гамильтоново блуждание в графе $ G $ - это прогулка, которая проходит через каждую вершину ровно один раз.
Если $ G $ - простой граф с n вершинами, где $ n \ geq 3 $ Если $ deg (v) \ geq \ frac {n} {2} $ для каждой вершины $ v $, то граф $ G $ является Гамильтонов граф. Это называетсяDirac's Theorem.
Если $ G $ - простой граф с $ n $ вершинами, где $ n \ geq 2 $, если $ deg (x) + deg (y) \ geq n $ для каждой пары несмежных вершин x и y, то граф $ G $ - гамильтонов граф. Это называетсяOre's theorem.
