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

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

точка

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

пример

точка

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

Линия

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

пример

линия

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

темя

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

пример

темя

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

край

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

пример

край

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

график

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

Пример 1

график

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

Пример 2

graph1

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

петля

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

Пример 1

петля

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

Пример 2

Петля 1

В этом графе есть две петли, которые сформированы в вершине 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 ребер.

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

Пример 2

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

Ненаправленный график 1

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

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

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

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

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

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

  • Степень вершины 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 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 '.

Пример 2

Смежность 1

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

  • 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

Мультиграф 1

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

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

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

Пример 1

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

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

Пример 2

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

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