Теория графов — основы

График — это диаграмма точек и линий, соединенных с точками. У него есть по крайней мере одна линия, соединяющая набор из двух вершин без вершин, соединяющих себя. Понятие графов в теории графов опирается на некоторые основные термины, такие как точка, линия, вершина, ребро, степень вершин, свойства графов и т. Д. Здесь, в этой главе, мы рассмотрим эти основы теории графов.

точка

Точка — это конкретная позиция в одномерном, двухмерном или трехмерном пространстве. Для лучшего понимания точку можно обозначить алфавитом. Его можно обозначить точкой.

пример

Здесь точка — это точка с именем «а».

Линия

Линия — это связь между двумя точками. Это может быть представлено сплошной линией.

пример

Здесь «а» и «б» являются точками. Связь между этими двумя точками называется линией.

темя

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

пример

Здесь вершина названа с алфавитом «а».

край

Ребро — это математический термин для линии, соединяющей две вершины. Многие ребра могут быть сформированы из одной вершины. Без вершины ребро не может быть сформировано. Для ребра должна быть начальная и конечная вершина.

пример

Здесь «a» и «b» — две вершины, и связь между ними называется ребром.

график

Граф ‘G’ определяется как G = (V, E), где V — множество всех вершин, а E — множество всех ребер графа.

Пример 1

В приведенном выше примере ab, ac, cd и bd являются ребрами графа. Аналогично, a, b, c и d являются вершинами графа.

Пример 2

В этом графе есть четыре вершины a, b, c и d и четыре ребра ab, ac, ad и cd.

петля

В графе, если ребро нарисовано от вершины к себе, это называется циклом.

Пример 1

На приведенном выше графике V — вершина, для которой у нее есть ребро (V, V), образующее петлю.

Пример 2

В этом графе есть две петли, которые сформированы в вершине a, и вершине b.

Степень вершины

Это число вершин, смежных с вершиной V.

Обозначение — град (V).

В простом графе с n числом вершин степень любых вершин равна —

deg(v) ≤ n – 1 ∀ v ∈ G

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

Степень вершины можно рассматривать по двум случаям графов —

• Ненаправленный граф
• Направленный граф

Степень вершины в неориентированном графе

Ненаправленный граф не имеет направленных ребер. Рассмотрим следующие примеры.

Пример 1

Посмотрите на следующий график —

На приведенном выше неориентированном графике

• deg (a) = 2, поскольку в вершине ‘a’ встречаются 2 ребра.

• deg (b) = 3, поскольку в вершине ‘b’ встречаются 3 ребра.

• deg (c) = 1, поскольку в вершине ‘c’ сформировано 1 ребро

  Итак, «c» — это вершина с кулоном .

• deg (d) = 2, поскольку в вершине ‘d’ встречаются 2 ребра.

• deg (e) = 0, так как в вершине ‘e’ есть 0 ребер.

  Так что «е» — изолированная вершина .

deg (a) = 2, поскольку в вершине ‘a’ встречаются 2 ребра.

deg (b) = 3, поскольку в вершине ‘b’ встречаются 3 ребра.

deg (c) = 1, поскольку в вершине ‘c’ сформировано 1 ребро

Итак, «c» — это вершина с кулоном .

deg (d) = 2, поскольку в вершине ‘d’ встречаются 2 ребра.

deg (e) = 0, так как в вершине ‘e’ есть 0 ребер.

Так что «е» — изолированная вершина .

Пример 2

Посмотрите на следующий график —

На приведенном выше графике

deg (a) = 2, deg (b) = 2, deg (c) = 2, deg (d) = 2 и deg (e) = 0.

Вершина «е» является изолированной вершиной. Граф не имеет никакой вершины.

Степень вершины в ориентированном графе

В ориентированном графе каждая вершина имеет степень и степень.

Степень графа

• Степень вершины V — это количество ребер, входящих в вершину V.

• Обозначение — град ^— (V).

Степень вершины V — это количество ребер, входящих в вершину V.

Обозначение — град ^— (V).

Степень графа

• Отступ вершины V — это число ребер, выходящих из вершины V.

• Обозначение — град ⁺ (V).

Отступ вершины V — это число ребер, выходящих из вершины V.

Обозначение — град ⁺ (V).

Рассмотрим следующие примеры.

Пример 1

Посмотрите на следующий ориентированный граф. Вершина «а» имеет два ребра, «ad» и «ab», которые идут наружу. Следовательно, его степень равна 2. Аналогично, существует ребро «ga», идущее к вершине «a». Следовательно, степень «а» равна 1.

Степень и степень других вершин показаны в следующей таблице:

темя	полустепень захода	полустепень
	1	2
б	2	0
с	2	1
d	1	1
е	1	1
е	1	1
г	0	2

Пример 2

Посмотрите на следующий ориентированный граф. Вершина ‘a’ имеет ребро ‘ae’, идущее наружу от вершины ‘a’. Следовательно, его степень равна 1. Аналогично, у графа есть ребро «ba», приближающееся к вершине «a». Следовательно, степень «а» равна 1.

Степень и степень других вершин показаны в следующей таблице:

темя	полустепень захода	полустепень
	1	1
б	0	2
с	2	0
d	1	1
е	1	1

Кулон Вертекс

Используя степень вершины, мы получаем два специальных типа вершин. Вершина с первой степенью называется нерешенной вершиной.

пример

Здесь, в этом примере, вершина ‘a’ и вершина ‘b’ имеют соединенное ребро ‘ab’. Таким образом, что касается вершины «a», то к вершине «b» имеется только одно ребро, и аналогично по отношению к вершине «b» есть только одно ребро к вершине «a». Наконец, вершина ‘a’ и вершина ‘b’ имеют степень как единицу, которая также называется висячей вершиной.

Изолированная вершина

Вершина с нулевой степенью называется изолированной вершиной.

пример

Здесь вершина «a» и вершина «b» не имеют связи между собой, а также с любыми другими вершинами. Таким образом, степень обеих вершин ‘a’ и ‘b’ равна нулю. Они также называются изолированными вершинами.

смежность

Вот нормы смежности —

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

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

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

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

Пример 1

На приведенном выше графике —

• «a» и «b» — это смежные вершины, так как между ними есть общее ребро «ab».

• «a» и «d» являются смежными вершинами, так как между ними есть общее ребро «ad».

• ab ‘и’ be ‘- смежные ребра, так как между ними есть общая вершина’ b ‘.

• be ‘и’ de ‘- смежные ребра, так как между ними есть общая вершина’ e ‘.

«a» и «b» — это смежные вершины, так как между ними есть общее ребро «ab».

«a» и «d» являются смежными вершинами, так как между ними есть общее ребро «ad».

ab ‘и’ be ‘- смежные ребра, так как между ними есть общая вершина’ b ‘.

be ‘и’ de ‘- смежные ребра, так как между ними есть общая вершина’ e ‘.

Пример 2

На приведенном выше графике —

• a ‘и’ d ‘являются смежными вершинами, так как между ними есть общее ребро’ ad ‘.

• ‘c’ и ‘b’ являются смежными вершинами, так как между ними есть общее ребро ‘cb’.

• ‘ad’ и ‘cd’ являются смежными ребрами, так как между ними есть общая вершина ‘d’.

• ac ‘и’ cd ‘являются смежными ребрами, так как между ними есть общая вершина’ c ‘.

a ‘и’ d ‘являются смежными вершинами, так как между ними есть общее ребро’ ad ‘.

‘c’ и ‘b’ являются смежными вершинами, так как между ними есть общее ребро ‘cb’.

‘ad’ и ‘cd’ являются смежными ребрами, так как между ними есть общая вершина ‘d’.

ac ‘и’ cd ‘являются смежными ребрами, так как между ними есть общая вершина’ c ‘.

Параллельные края

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

На приведенном выше графике «a» и «b» — это две вершины, которые соединены между собой двумя ребрами «ab» и «ab». Так это называется параллельным ребром.

Мульти График

Граф, имеющий параллельные ребра, называется мультиграфом.

Пример 1

На приведенном выше графике есть пять ребер «ab», «ac», «cd», «cd» и «bd». Поскольку ‘c’ и ‘d’ имеют два параллельных ребра между ними, это мультиграф.

Пример 2

На приведенном выше графике вершины «b» и «c» имеют два ребра. Вершины ‘e’ и ‘d’ также имеют два ребра между ними. Следовательно, это мультиграф.

Степень последовательности графика

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

Пример 1

темя		б	с	d	е
Присоединенный к	До нашей эры	объявление	объявление	с, Ь, е	d
степень	2	2	2	3	1

На приведенном выше графике для вершин {d, a, b, c, e} последовательность степеней равна {3, 2, 2, 2, 1}.

Пример 2

темя		б	с	d	е	е
Присоединенный к	быть	а, с	б, г	с, е	объявление	—
степень	2	2	2	2	2	0

На приведенном выше графике для вершин {a, b, c, d, e, f} последовательность степеней равна {2, 2, 2, 2, 2, 0}.