40 Способы задания графов.

Рисунок.

Список вершин и рёбер.

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

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

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

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

41 Смежность, инцидентность.

Две вершины  и , где V – множество вершин графа G, называются смежными, если они соединены ребром. Два ребра называются смежными, если они имеют общую вершину.

Если вершина является концом ребра, то вершина и ребро называются инцидентными.

Число ρ(v) ребер, инцидентных вершине v, называется степенью этой вершины v. 

Степень изолированной вершины равна нулю. Степень изолированной вершины, содержащей одну петлю, равна 2.

Вершина, степень которой равна 1, называется висячей.

Сумма степеней всех вершин графа есть четное число.

Половина суммы степеней всех вершин равна числу всех ребер графа (любого, в том числе псевдографа и мультиграфа). 

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

где n – число вершин графа;

      ρ(i) – степень i-й вершины графа ( i = 1, 2, … , n).

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

Степень любой вершины полного графа равна n–1,

где n – число его вершин, так как каждая вершина соединена ребрами с остальными вершинами графа. Отсюда следует, что числоK ребер полного графа  равно:

42.Операции над графами. Части графов.

Пусть граф G содержит множество V вершин и множество Е ребер.

Определим некоторые операции на графах:

1. Удаление или добавление ребра;

2. Удаление вершины. Из множества вершин удаляем выбранную вершину, а из множества ребер все инцидентные ей ребра;

3. Стягивание ребра. Отождествляем (стягиваем) вершины инцидентные выбранному ребру;

4. Добавление вершины (разбиение ребра). Выберем некоторое ребро (u,v) из множества ребер и удалим его. В множество вершин добавим новую вершину w, а в множество ребер новые ребра (u,w) и (w,v);

5. Объединение графов. Объединением графов иназывают граф, где ;

6. Пересечение графов. Пересечением двух графов G₁ и G₂ называется граф , где , .

Маршрутом длины n называется непустая последовательность n ребер вида:

v1, e1, v2, e2, v3, e3, …, vn , en, vn+1,

.

где ребро e_j  (j = 1, 2, …, n) соединяет вершины v_j и v_j+1 . Очевидно, что в последовательности. одни и те же вершины могут повторяться.

Маршрут называется цепью, если в нем нет повторяющихся ребер. 

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

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

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

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

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

Число ребер, входящих в цепь, называется длиной цепи или расстоянием между соответствующими вершинами

Обхватом графа называется длина его кратчайшего цикла.