Как найти степень вершины ориентированного графа

Определение
7.10. Степенью
вершины v
для неориентированного графа, обозначается
d(v),
называется количество ребер, инцидентных
этой вершине. Вершина степени 0 называется
изолированной.
Вершина степени 1 называется висячей.

Определение
7.11. Полустепенью
исхода вершины
v
для орграфа
называется количество дуг, для которых
v
является начальной вершиной, обозначается
.

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

Теорема 7.2.
(Теорема
Эйлера)
Сумма степеней вершин графа равна
удвоенному количеству ребер:

.

Доказательство.
При подсчете суммы степеней вершин
каждое ребро учитывается два раза: для
одного конца ребра и для другого.

Следствие 1.
Число вершин нечетной степени четно.

Доказательство.
По теореме Эйлера сумма степеней всех
вершин – четное число. Сумма степеней
вершин четной степени четна, значит,
сумма степеней вершин нечетной степени
также четна, следовательно, их четное
число.

Следствие 2.
Сумма полустепеней вершин орграфа
равна удвоенному количеству дуг:

.

Доказательство.
Сумма полустепеней вершин орграфа
равна сумме степеней вершин графа,
полученного из орграфа забыванием
ориентации дуг.

Пример 7.5.
Определить степени вершин данного
графа.

Пример 7.6.
Определить полустепени исхода и захода
данного орграфа.

7.5. Представление (способы задания) графов.

1. Граф
   как алгебраическая система:

модель, носителем
которой является множество вершин, а
отношение – бинарное отношение смежности
вершин.

< {a,b,c,d};
— множество
вершин

{(a,b),(b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)}
– множество
рёбер
>

1. Геометрический

Получается путём
расположения различных точек на
плоскости для каждой вершины vÎV,
причём если (v₁,v₂)ÎЕ,
то проводится ребро (дуга) из v₁
в v₂.

Для представления
в компьютере чаще всего граф задается
либо матрицей
смежности,
либо матрицей
инциденций.

Матрицей
смежности вершин неориентированного
графа
G,
содержащего n
вершин, называют квадратную матрицу
A=a_ij
n-го
порядка, у которой строки и столбцы
матрицы соответствуют вершинам
неориентированного графа.

Элементы a_ij
матрицы A
равны числу ребер, направленных из i-й
вершины в j-ю.
В случае неориентированного
графа G
ему вместе с ребром (v_i,
v_j)
принадлежит и ребро (v_j,
v_i),
поэтому матрица смежности вершин
A=a_ij
будет симметрична относительно главной
диагонали.

ПРИМЕР.
Граф: множество вершин V
= {a,b,c,d,e}

Множество
ребер

Е
= {{а, b},
{а, е}, {b,
c},
{b,
d},
{c,
e},
{d,e}},

Матрица смежности
симметрична относительно главной
диагонали.

На главной диагонали
стоит 1 (символ Л) из-за
нерефлексивности
отношения на множестве вершин (EÍV´V)

Логическая матрица
отношения на множестве вершин графа,
которое задается его ребрами.

a b c d

a 0 1 0 1

b 1 0 1 1

с 0 1 0 1

d 1 1 1 0

простой
граф

a b c d

a 1 1 0 1

b 1 0 3 0

c 0 3 0 2

d 1 0 2 0

граф
с кратными

рёбрами
и петлёй

Определение
7.12. Матрица
смежности вершин орграфа
G,
содержащего n
вершин-
это квадратная матрица A=a_ij
n-го
порядка, у которой строки и столбцы
матрицы соответствуют вершинам орграфа.

Элементы a_ij
матрицы A
равны числу дуг, направленных из i-й
вершины в j-ю.
Если орграф состоит из однократных
дуг, то элементы матрицы равны либо 0,
либо 1.

Матрица
смежности:

Пусть дан граф G,
его матрица
смежности
А = [a_ij]
определяется следующим образом:

a_ij
= 1 если в G
существует дуга (x_i,
x_j)

a_ij
= 0 если в G
нет дуги (x_i,
x_j)

Определение
7.14. Матрицей
инциденций (инцидентности) неориентированного
графа с
вершинами
и
ребрами
называется
матрица
размерности,
строки которой соответствуют вершинам,
а столбцы – ребрам. Элементыматрицы инциденций неориентированного
графа равны 1, если вершинаинцидентна ребру,
и 0 в противном случае.

Матрицей
инциденций (инцидентности) орграфа с
вершинами
и
дугами
называется
матрица
размерностиnm,
строки которой соответствуют вершинам,
а столбцы -дугам
орграфа.

Элементы c_ij
равны

1, если дуга e_j
исходит из i-й
вершины;

–1, если дуга e_j
заходит в i-ю
вершину;

0, если дуга не
инцидентна i-й
вершине

Поскольку каждая
дуга инцидентна двум различным вершинам,
за исключением того случая, когда дуга
образует петлю, то каждый столбец либо
содержит один элемент, равный 1, и один
– равный –1, либо все элементы столбца
равны 0.

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

В каждом столбце
также будут две единицы, так как каждое
ребро инцидентно двум вершинам.

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

Поэтому, используя
матрицу инцидентности, нельзя восстановить
ориентированный граф.

Такую возможность
обеспечивает матрица смежности,

Пример
7.7.1.
Для заданного неориентированного
графа построить матрицы смежностей и
матрицу инциденций.

Решение.
1) Строим матрицу смежности вершин,
которая будет размерности 44.
Строим матрицу смежности ребер, которая
будет размерности 55.

2) Строим матрицу
инциденций, которая будет размерности
45.

Пример
7.7.2.
Для заданного ориентированного графа
построить матрицы смежностей и матрицу
инциденций.

Решение.
1) Строим матрицу смежности вершин,
которая будет размерности 44.
Строим матрицу смежности ребер, которая
будет размерности 55.

2) Строим матрицу
инциденций, которая будет размерности
45.

import java.util.*;

class GFG {

    static void findInOutDegree(List<List<Integer> > adjList, int n)

    {

        int in[] = new int[n];

        int out[] = new int[n];

        for (int i = 0; i < adjList.size(); i++) {

            List<Integer> list = adjList.get(i);

            out[i] = list.size();

            for (int j = 0; j < list.size(); j++)

                in[list.get(j)]++;

        }

        System.out.println("VertextIntOut");

        for (int k = 0; k < n; k++) {

            System.out.println(k + "t" + in[k] + "t" + out[k]);

        }

    }

    public static void main(String args[])

    {

        List<List<Integer> > adjList = new ArrayList<>();

        List<Integer> tmp =

           new ArrayList<Integer>(Arrays.asList(1, 2));

        adjList.add(tmp);

        tmp = new ArrayList<Integer>(Arrays.asList(3));

        adjList.add(tmp);

        tmp =

          new ArrayList<Integer>(Arrays.asList(0, 5, 6));

        adjList.add(tmp);

        tmp = new ArrayList<Integer>(Arrays.asList(1, 4));

        adjList.add(tmp);

        tmp = new ArrayList<Integer>(Arrays.asList(2, 3));

        adjList.add(tmp);

        tmp = new ArrayList<Integer>(Arrays.asList(4, 6));

        adjList.add(tmp);

        tmp = new ArrayList<Integer>(Arrays.asList(5));

        adjList.add(tmp);

        int n = adjList.size();

        findInOutDegree(adjList, n);

    }

}

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

точка

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

пример

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

Линия

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

пример

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

темя

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

пример

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

край

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

пример

Здесь «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.

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

Пример 2

Посмотрите на следующий ориентированный граф. Вершина ‘a’ имеет ребро ‘ae’, идущее наружу от вершины ‘a’. Следовательно, его степень равна 1. Аналогично, у графа есть ребро «ba», приближающееся к вершине «a». Следовательно, степень «а» равна 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, a, b, c, e} последовательность степеней равна {3, 2, 2, 2, 1}.

Пример 2

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

Степень или валентность вершины графа — количество рёбер графа G <displaystyle G> , инцидентных вершине x <displaystyle x> . При подсчёте степени ребро-петля учитывается дважды. [1]

Степень вершины обычно обозначается как d ( x ) <displaystyle d(x)> или deg ⁡ ( v ) <displaystyle deg(v)> . Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.

Содержание

Лемма о рукопожатиях [ править | править код ]

По формуле суммы степеней для графа G = ( V , E ) <displaystyle G=(V,E)> ,

∑ v ∈ V deg ⁡ ( v ) = 2 | E | , <displaystyle sum _deg(v)=2|E|,,>

то есть сумма степеней вершин любого графа равна удвоенному числу его рёбер. Кроме того, из формулы следует, что в любом графе число вершин нечётной степени чётно. Данное утверждение (и сама формула) известны как лемма о рукопожатиях. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других, чётно.

Последовательность степеней вершин [ править | править код ]

Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью. [2] Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0). Последовательность степеней вершин есть инвариант графа, поэтому у изоморфных графов она одинакова. Однако последовательность степеней вершин не является уникальной характеристикой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью.

Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин). Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (англ. graphical sequence ). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 3, 3, 1) не может быть последовательностью степеней графа. Обратное также верно: если последовательность имеет чётную сумму, она представляет собой последовательность степеней мультиграфа. Построение такого графа осуществляется достаточно простым способом: необходимо объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам следует добавить петли.

Сложнее реализовать простой граф с заданной последовательностью. Теорема Эрдёша — Галлаи утверждает, что невозрастающая последовательность d_i (при i = 1,…,n) может быть последовательностью простого графа только если её сумма чётна и выполняется неравенство

∑ i = 1 k d i ≤ k ( k − 1 ) + ∑ i = k + 1 n min ( d i , k ) k ∈ < 1 , … , n − 1 >. <displaystyle sum _^d_leq k(k-1)+sum _^min(d_,k)quad kin <1,dots ,n-1>,.>

Например, последовательность (3, 3, 3, 1) не может являться последовательностью простого графа; она удовлетворяет неравенству Эрдёша — Галлаи только при k равном 1, 2 или 4, но не при k равном 3.

Согласно критерию Гавела — Хакими, если невозрастающая последовательность (d₁, d₂, …, d_n) это последовательность степеней простого графа, то (d₂ − 1, d₃ − 1, …, d_d1+1 − 1, d_d1+2, d_d1+3, …, d_n) некоторая последовательность степеней простого графа. Этот факт позволяет построить полиномиальный алгоритм нахождения простого графа с заданной реализуемой последовательностью.

Сопоставим исходной последовательности чисел вершины графа без ребер с требуемыми степенями. Указанное преобразование последовательностей задает как минимум одну вершину графа, все инцидентные ей ребра и множество вершин с новыми требуемыми дополнениями степеней. Упорядочивая оставшиеся вершины по невозрастанию дополнений степеней, получим невозрастающую последовательность степеней простого графа. Повторяя преобразование и упорядочение не более n-1 раза, получаем весь граф.

Проблема нахождения или оценки числа графов по заданной последовательности относится к области перечисления графов.

Теория графов

Графы

Бинарное отношение на конечном множестве X есть ориентированный конечный граф (орграф) RÍX 2 . Таким образом, всякий орграф определяется множествами:

X=₁,X₂,…,X_n> – множеством вершин графа и множеством упорядоченных пар (кортежей)

Общепринято обозначать орграфы в виде

X – множество вершин орграфа;

U – множество дуг орграфа, или в виде

ГX = <Гx₁,Гx₂,…,Гx_n> – множество образов элементов множества X, т.е. отображение X в X, понимая термин отображения как точечно-множественное отображение.

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

При геометрической реализации неориентированного графа вместо двух дуг и , соединяющих вершины X_i и X_j, употребляется одно ребро (X_i,X_j), не имеющее ориентации. На рис. 3.1.1 приведены геометрические реализации орграфов (слева) и их неориентированных аналогов – неориентированных графов (справа). G(X,U), если X’ÍX; U’ÍU, т.е. подграф G’ получим из графа G, если уберем какое-либо число вершин или ребер (дуг).

Две вершины графа называются смежными, если они соединены с началом другой.

Дуги называются смежными, если конец одной из них совпадает с началом другой.

Некоторая последовательности смежных дуг называется путем, а последовательность смежных ребер называется цепью.

Замкнутый путь называется контуром, а замкнутая цепь – циклом.

Сформулированные определения удобно представить в виде следующей таблицы:

Рассмотрим еще некоторые определения, которые нам понадобятся в дальнейшем. Пусть (цепь) называется элементарным, если он проходит через вершины графа по одному разу.

Путь (цепь) называется простым, если он проходит через дуги графа по одному разу. В противном случае путь (цепь) называется составным. Аналогично определяются и простые контуры и циклы.

Цепь (цикл) называется гамильтоновой, если она проходит через все вершины графа по одному разу, т.е. элементарная цепь, проходящая через все вершины графа, есть гамильтонова цепь.

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

Аналогично определяются гамильтоновы и эйлеровы путь и контуры.

Симметричный граф Неориентированный граф

Граф-толерантность Неориентированный граф

Граф-толерантность Неориентированный граф

Граф-декартово произведение Неориентированный полный граф

(с полным насыщением)

Степень вершины графа. Число ребер графа.

Вершина X_i называется инцидентной дуге (ребру) графа, если она является началом или концом этой дуги (ребра).

Степенью вершины графа называют число дуг (ребер), инцидентных данной вершине. Степень обозначается P(X_i).

Для ориентированного графа различают полустепень захода P + — число дуг, входящих в данную вершину, и полустепень исхода P — — число дуг, выходящих из данной вершины. Степень вершины ориентированного графа составит сумма полустепеней исхода и захода.

Если для некоторой вершины ориентированного графа полустепень захода некоторой вершины P + =0 и при этом полустепень исхода P — ¹0, то вершина называется входом графа.

Если для некоторой вершины ориентированного графа P — =0, а P + ¹0, то вершина называется выходом графа.

Граф, изображенный на рис. 3.1.2, имеет один вход – вершину X

Число ребер графа N связано со степенями его вершин следующим соотношением:

N= ,

где n – число вершин графа. Отсюда следует справедливость следующих утверждений:

1) Сумма степеней вершин любого графа четна;

2) Для любого графа число вершин, имеющих нечетные степени, четно;

3) Для однородного графа, т.е. графа, все степени вершин которого одинаковы и равны r, N= ;

4) Для полного графа, т.е. графа, в котором каждая пара вершин соединена ребром или дугой, P(X_i)=n-1, а N= .

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

Связность

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

Существует другое определение связности графа. Граф называется связным, если две любые его вершины можно соединить цепью. Граф (рис. 3.1.3) является несвязным с двумя компонентами.

Ребро графа называется перешейком, или связующей линией, если его удаление приводит к тому, что граф становится несвязным. На рис. 3.1.4 изображены три связных неориентированных графа, причем граф 1 не имеет ни одного перешейка, 2 содержит один перешеек (отмечен жирной линией), граф 3 целиком состоит из одних перешейков. Такой граф (3) называется деревом.

Определение 7.10. Степенью вершины v для неориентированного графа, обозначается d(v), называется количество ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей.

Определение 7.11. Полустепенью исхода вершины v для орграфа называется количество дуг, для которых v является начальной вершиной, обозначается .

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

Теорема 7.2. (Теорема Эйлера) Сумма степеней вершин графа равна удвоенному количеству ребер:

.

Доказательство. При подсчете суммы степеней вершин каждое ребро учитывается два раза: для одного конца ребра и для другого.

Следствие 1. Число вершин нечетной степени четно.

Доказательство. По теореме Эйлера сумма степеней всех вершин – четное число. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, следовательно, их четное число.

Следствие 2. Сумма полустепеней вершин орграфа равна удвоенному количеству дуг:

.

Доказательство. Сумма полустепеней вершин орграфа равна сумме степеней вершин графа, полученного из орграфа забыванием ориентации дуг.

7.5. Представление (способы задания) графов.

Граф как алгебраическая система:

модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин.

Получается путём расположения различных точек на плоскости для каждой вершины vÎV, причём если (v₁,v₂)ÎЕ, то проводится ребро (дуга) из v₁ в v₂.

Для представления в компьютере чаще всего граф задается либо матрицей смежности, либо матрицей инциденций.

Матрицей смежности вершин неориентированного графа G, содержащего n вершин, называют квадратную матрицу A=a_ij n-го порядка, у которой строки и столбцы матрицы соответствуют вершинам неориентированного графа.

Элементы a_ij матрицы A равны числу ребер, направленных из i-й вершины в j-ю. В случае неориентированного графа G ему вместе с ребром (v_i, v_j) принадлежит и ребро (v_j, v_i), поэтому матрица смежности вершин A=a_ij будет симметрична относительно главной диагонали.

ПРИМЕР. Граф: множество вершин V =

Матрица смежности симметрична относительно главной диагонали.

На главной диагонали стоит 1 (символ Л) из-за нерефлексивности отношения на множестве вершин (EÍV´V)

Логическая матрица отношения на множестве вершин графа, которое задается его ребрами.

a b c d