Графики и графические модели

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

Две дискретные структуры, которые мы рассмотрим, - это графы и деревья. Граф - это набор точек, называемых узлами или вершинами, которые связаны между собой набором линий, называемых ребрами. Изучение графиков, или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.