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

Ничего не сделано, если что-то осталось недоделанным. – Иоганн Гаусс

В этой статье:

• Смежность и инцидентность

• Петли

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

Давайте рассмотрим самый обыкновенный неориентированный граф (Рисунок 1). В нем есть вершина Р и вершина К. Данные вершины являются смежными (adjacent), так как они соединены ребром РК.

Помимо этого, как мы видим, вершина К является концом ребра РК, а Р его началом, в таких случаях вершина К и Р называются инцидентными (incident) ребру РК.

Смежностью вершин графа – называется отношение между двумя вершинами, в котором существует ребро их соединяющее.

Инцидентность – это когда вершина a является началом или концом ребра t. Если мы добавим еще одну вершину b, то мы скажем, что вершина a и b инцидента ребру t.

Кроме вершин, смежность присутствует и у рёбер. Рёбра просто должны иметь общую вершину. В нашем случаи мы можем сказать, что ребро ДК является смежным ребру РК, так как у них есть общая вершина К.

Смежностью рёбер графа – называется отношение между двумя рёбрами, в котором существует вершина соединяющая их.

В связи с тем, что выше мы рассматривали неориентированный граф, то было неважно, с какого направления определять смежность и инцидентность. Вершина Р могла быть смежна вершине К, но также мы могли сказать, что вершина К смежна вершине Р.

В ориентированном графе все немного по-другому (Рисунок 2), так у нас имеется направление, которое мы не в силах поменять. Если вершина 1 смежна вершине 2, то вершина 2 не может быть смежна вершине 1. То же самое касается и инцидентности. Вершины 1 и 2 инцидентны ребру 12, наоборот не работает.

Петли

Петля – это ребро инцидентное одной и той же вершине. То есть вершина которая соединена сама с собой. На рисунке ниже мы видим, как это выглядит.

Заключение

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

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

Какие статьи хотели бы почитать?

Проголосовали 26 пользователей.

Воздержались 9 пользователей.

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

self_loop(Node):-
  edge(Node, Node).

Однако для поиска циклов граф удобнее преобразовать в список (не использовать записи базы данных), т.к. при поиске в ширину пройденные дуги удобно удалять, но при этом не хотелось бы испортить исходный граф. При этом если вы используете SWI Prolog, то записи базы данных могли бы быть такими — edge(From, To), однако при использовании Visual Prolog с этим могли бы возникнуть проблемы — чтобы получить набор дуг можно хранить в базе данных записи следующего вида: data(edge(From, To)). Формат записей не сильно скажется на функции сбора всех записей в список:

database_to_graph_list(Graph):-
  findall(Edge, data(Edge), Graph).

Теперь наш граф представлен в виде списка, для поиска элемента в котором можно применять функцию member, а для удаления — delete. Для поиска цикла (т.е. пути, начало и конец которого совпадают) из некоторой вершины мы можем:

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

loop_graph(A, Graph, ProcessedNodes, [A|ProcessedNodes]):-
  member(edge(A, X), Graph),
  member(X, [A|ProcessedNodes]), !.
loop_graph(A, Graph, ProcessedNodes, [A|Loop]):-
  member(edge(A, X), Graph),
  delete(Graph, edge(A, X), NewGraph),
  loop_graph(X, NewGraph, [A|ProcessedNodes], Loop).

Данный фрагмент ищет не только циклы, но и петли благодаря тому, что к списку пройденных вершин в последнем вызове member в первом правиле добавляется исходный узел.
Приведенный фрагмент кода вернет все найденные циклы с началом в заданной вершине. Для того, чтобы получить все циклы в графе нужно оставить начальную вершину анонимной. При этом, если мы захотим проверить является ли граф деревом, мы должны будем использовать оператор NOT:
NOT(loop_graph(_X, Graph, [], _Loop))
Однако Visual Prolog при этом вернет ошибку, связанную с тем, что цель оператора NOT содержит анонимную переменную:

Free variable are not allowed in ‘not’ or ‘retractall’

Для решения проблемы достаточно написать вспомогательную функцию, выполняющую поиск любого цикла или петли в графе:

loop_graph(Graph):-
  loop_graph(_X, Graph, [], _Loop), !.

Вызов такой функции не содержит анонимных переменных, поэтому может использоваться совместно с оператором NOT.

На скриншоте показаны циклы, которые программа найдет для заданного Вами графа.

Информатика. Учебник для 9 класса (по учебнику К. Ю. Полякова, Е.А. Еремина, базовый уровень) 

§17. Графы.

---

Что такое граф?

Ключевые слова:

• граф	
• вершина	
• ребро	
• матрица смежности	
• степень вершины	
• связный граф
• взвешенный граф
• весовая матрица
• ориентированный граф
• оптимальный путь
• количество путей

Давайте подумаем, как можно наглядно представить такую информацию:

От пос. Васюки три дороги идут в Солнцево, Грибное и Ягодное. Между Солнцевом и Грибным и между Грибным и Ягодным также есть дороги. Кроме того, есть дорога, которая идет из Грибного в лес и возвращается обратно в Грибное.
Нарисуйте в тетради схему дорог по этому описанию.

Можно, например, нарисовать такую схему (рис. 3.17, а).

Рис. 3.17

В информатике для исследования таких схем используют графы.

Граф — это набор вершин (узлов) и связей между ними — рёбер.

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

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

Для хранения информации об узлах и связях показанного выше графа можно использовать таблицу такого вида (рис. 3.18).

Рис. 3.18

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

Исследуйте матрицу смежности и сравните её с графом на рис. 3.17, б. Что означает единица на пересечении столбца С и строки С?

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

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

Подсчитайте по матрице смежности, сколько ребёр в графе. Определите степени всех вершин. Как вы рассуждали?

Строго говоря, граф — это математический объект, а не рисунок. Конечно, его можно нарисовать на плоскости (например, как на рис. 3.17, б), но матрица смежности не даёт никакой информации о том, как именно располагать вершины друг относительно друга. Для таблицы, приведённой выше, возможны, например, такие варианты (рис. 3.19).

Рис. 3.19

Нарисуйте по матрице смежности (рис. 3.20) два разных изображения графа.

Рис. 3.20

Граф имеет 4 вершины, причём каждая вершина связана рёбрами со всеми остальными. Нарисуйте этот граф. Сколько всего рёбер в этом графе?

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

Граф имеет 4 ребра. Чему равна сумма степеней вершин в этом графе? Зависит ли она от количества вершин?

Граф имеет N рёбер. Чему равна сумма степеней вершин в этом графе?

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

Связный граф

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

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

Теперь представьте себе, что дороги Васюки-Солнцево, Васю- ки-Грибное и Грибное-Ягодное завалило снегом (или размыло дождём) так, что по ним ни пройти, ни проехать (рис. 3.21).

Рис. 3.21

Эту схему тоже можно считать графом (она соответствует определению), но в таком графе есть две несвязанные части, каждая из которых — связный граф. Такие части называют компонентами связности.

Постройте матрицу смежности графа, изображённого на рис. 3.21.

Граф имеет 4 вершины и две компоненты связности. Какое наибольшее количество рёбер может быть в этом графе, если в нём нет петель? Нарисуйте этот граф.

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

Найдите все циклы в графе на рис. 3.17.

Дерево — это связный граф, в котором нет циклов.

Взвешенный граф

Если в нашем примере нас заинтересует не только наличие дорог между посёлками, но ещё и расстояния между ними, каждой связи нужно сопоставить число — вес ребра (рис. 3.22).

Рис. 3.22

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

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

Как хранить информацию о таком графе? Ответ напрашивается сам собой — нужно в таблицу записывать не 1 или 0, а вес ребра. Если связи между двумя узлами нет, на бумаге можно оставить ячейку таблицы пустой, а при хранении в памяти компьютера записывать в неё условный код, например, число -1 или очень большое число. Такая таблица называется весовой матрицей, потому что содержит веса рёбер. В данном случае она выглядит так (рис. 3.23).

Рис. 3.23

Так же как и матрица смежности, весовая матрица симметрична относительно диагонали.

Что означают пустые ячейки в весовой матрице?

Как по весовой матрице сразу определить, сколько рёбер в графе?

Определите по весовой матрице (рис. 3.24) длины путей ADBEC, ABDCE, DEBAC. Как вы рассуждали?

Рис. 3.24

Оптимальный путь в графе

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

Какие показатели вы используете в жизни для определения оптимального пути? Всегда ли самый короткий путь — самый лучший?

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

Рис. 3.25

Найдём наилучший путь из А в В — такой, при котором общая стоимость поездки минимальная.

Для решения задачи будем строить дерево перебора вариантов. Видим, что из пункта А напрямую

Рис. 3.26

Числа около рёбер обозначают стоимость поездки по этому участку, а индексы у названий узлов показывают общую стоимость проезда в данный узел из узла А. Теперь разберём варианты дальнейшего движения из узла С I tM lt;pb р (рис. 3.27).

Рис. 3.27

Почему, на ваш взгляд, на схеме не показана возможность движения из С в А?

Видим, что из С сразу можно попасть в В, стоимость проезда в этом случае равна 7.

Почему нельзя на этом остановиться, ведь путь из А в В найден?

Проверяя пути через узел В, выясняем, что можно сократить стоимость до 6 (рис. 3.28)

Рис. 3.28

Нужно ли исследовать дальше путь, содержащий цепочку ACED? Сравните стоимость этого пути и стоимость уже найденного пути из А в В.

Аналогично строим вторую часть схемы (рис. 3.29).

Рис. 3.29

Таким образом, оптимальный (наилучший) путь — ADEB, его стоимость — 3.

Нужно ли проверять пути ACED и ADEC, не дошедшие до узла В? Могут ли они улучшить результат?

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

Ориентированный граф

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

Ориентированный граф (орграф) — это граф, в котором каждое ребро имеет направление.

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

На схеме на рис. 3.30 всего две дороги с двусторонним движением, по остальным можно ехать только в одну сторону.

Рис. 3.30

Рёбра в орграфе называют дугами. Дуга, в отличие от ребра, имеет начало и конец.

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

Рис. 3.31

---

Количество путей

Определим количество возможных путей из вершины А в вершину К для ориентированного графа, показанного на рис. 3.32.

Рис. 3.32

Так как граф ориентированный, переходить в другую вершину можно только по стрелкам.

В графе на рис. 3.32 есть одна начальная вершина А, из которой дуги только выходят. Такая вершина называется истоком. Вершина, в которую дуги только входят (и ни одна не выходит), называется конечной вершиной или стоком. В нашем графе сток — это вершина К.

По весовой матрице на рис. 3.31 найдите исток и сток в графе. Как вы рассуждали?

Будем двигаться по стрелкам от начальной вершины А. Около каждой вершины запишем количество возможных путей из вершины А в эту вершину. В вершину А существует единственный путь — пустой (никуда не ехать). Найдём все вершины, в которые можно приехать только из А: это вершины Б и Г, записываем около них количество путей 1 (рис. 3.33).

Рис. 3.33

Теперь ищем вершины, в которые можно попасть только из уже отмеченных вершин. Например, в вершину В есть один путь из А напрямую, а также по одному пути через Б и Г (так как эти вершины отмечены числом 1). Общее количество путей из А в Б равно сумме отметок предыдущих вершин: для вершины В получаем 3 пути. В вершину Ж можно попасть только из Г, поэтому число путей в Г и Ж совпадает (рис. 3.34).

Рис. 3.34

В вершину Д идёт один путь через Б и три пути через В, поэтому общее число путей — 4. Аналогично получаем 4 пути в вершину Е: 3 пути через В и один через Ж (рис. 3.35).

Рис. 3.35

Далее находим один путь из А в И (только через Ж) и 4 пути из А в 3 (все через Д). В конечную вершину К можно приехать через вершины Д (4 пути), 3 (4 пути), Е (4 пути) и И (1 путь), таким образом, общее количество различных путей равно 13 (рис. 3.36).

Рис. 3.36

---

Выводы

• Граф — это набор вершин (узлов) и связей между ними — рёбер.
• Матрица смежности — это таблица, в которой единица на пересечении строки и столбца обозначает ребро между соответствующими вершинами, а ноль — отсутствие ребра.
• Связный граф — это граф, между любыми вершинами которого существует путь.
• Цикл — это замкнутый путь в графе.
• Дерево — это связный граф, в котором нет циклов.
• Взвешенный граф — это граф, с каждым ребром которого связано некоторое число — вес ребра. Взвешенный граф описывается весовой матрицей.
• Ориентированный граф (орграф) — это граф, в котором каждое ребро имеет направление. Рёбра орграфа называют дугами. Матрица смежности и весовая матрица орграфа могут быть несимметричными.

Нарисуйте в тетради интеллект-карту этого параграфа.

---

Вопросы и задания

1. Можно ли сказать, что лес (множество деревьев) — это граф? Почему?
2. Как по матрице смежности определить, есть ли петли в графе?
3. Как по весовой матрице определить длину пути в графе?
4. Когда для представления данных используются орграфы? Приведите примеры.
5. Выполните по указанию учителя задания в рабочей тетради.

---

Оглавление

§16. Списки и деревья.

§17. Графы.

§18. Игровые стратегии.

---

Основные понятия теории графов

Теория графов – раздел конечной математики. Особенность
данного раздела – геометрический подход к изучению объектов. Понятие графа
опирается на основные понятия теории множеств. Граф можно рассматривать как
объект, состоящий из двух множеств — множества точек (вершин) X и множества линий
(рёбер) U, которые
соединяют некоторые вершины. При этом совершенно несущественно, соединены ли
вершины графа отрезками прямых линий или криволинейными дугами, какова длина
линий, как расположены вершины графа на плоскости и другие геометрические
характеристики графа. Каждое ребро представляет собой неупорядоченную пару
вершин из множества X.

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

G = (X, U)                                                        (1)

где X – множество вершин; U – множество рёбер.

Пример
изображения графа G, состоящего из множества вершин X = {x₁, x₂, x₃, x₄, x₅} и множества рёбер U = {u₁₂, u₁₃, u₁₄, u₁₅, u₂₄, u₂₅, u₃₅} представлен на
рис. 1.

Рис. 1

Элементы
множеств X и U могут содержать индексы.
Индексы вершин обозначают их номера. Индексы рёбер обозначают номера
соединяемых ими вершин. Запись u_ij означает, что ребро графа образовано парой
вершин x_i x_j:

u_ij = (x_i,
x_j), x_i, x_j Î X,

Виды графов. Основные понятия
и определения

Конечный граф – это граф G = (X, U), у которого количество его вершин |X| конечно. Конечный граф
представлен на рис. 1.

Нуль-граф – это граф G = (X, U), состоящий только из
изолированных вершин, т.е. граф, не содержащий ни одного ребра (|U| = 0). Такой граф обозначается
G₀. Нуль-граф, у
которого |X| = 5 и |U| = 0 представлен на рис.
2.

Рис. 2

Пустой граф – это граф G = (X, U), не содержащий ни вершин, ни рёбер (|X| =0, |U| = 0). Такой граф
обозначается G_Ø.

Неориентированный граф (неограф) — это граф G = (X, U), для каждого рёбра которого
несуществен порядок двух его концевых вершин. Неограф представлен на рис. 1.
Рёбра неографа иногда называют звеньями.

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

Смешанный граф
(рис. 3.10) – это граф, который содержит как ориентированные, так и
неориентированные рёбра. Смешанный граф обозначается .

Любой
из перечисленных видов графа может содержать одно или несколько рёбер, у
которых оба конца сходятся в одной вершине, т.е. u_ij Î U,

u_ij = (x_i, x_j), i = j. Такие рёбра называются петлями.
На рис. 5 представлен смешанный граф с петлями.

В общем случае множество рёбер U может состоять из трёх непересекающихся
подмножеств: подмножества звеньев, подмножества дуг и подмножества петель.

Ребро u_ij, соединяющее вершины x_i и x_j, инцидентно
данным вершинам и наоборот, вершины x_i и x_j инцидентны ребру u_ij. Ребро u₁₂ (рис. 1) инцидентно вершинам x₁ и x₂, а вершины x₁ и x₂, в свою
очередь,  инцидентны ребру u₁₂.

Мультиграф (рис. 6) – это граф, у которого любые две вершины
соединены более чем одним ребром. Рёбра, соединяющие одну и ту же пару вершин,
называются кратными. Наибольшее число кратных рёбер, соединяющих
какую-либо пару вершин, называется мультичислом. Мультичисло графа, представленного
на рис. 6, m = 5.

Скелет мультиграфа
– это граф, полученный из исходного мультиграфа путём удаления петель и
сведения кратных рёбер в одно ребро. На рис. 7 показан скелет мультиграфа,
представленного на рис. 6.

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

Плотный граф – это полный граф, у которого при каждой вершине
имеется петля. Плотный граф представлен на рис. 9 и обозначается G_пʹ.

Смежными вершинами называются любые две вершины x_i, x_j Î X графа G = (X, U), инцидентные одному и
тому же ребру. Так, например, вершины x₁ и x₂ (рис. 1) являются смежными, а вершины x₄ и x₅ смежными не
являются, так как не соединены между собой, т.е. ребро u₄₅ отсутствует.

Смежными рёбрами называются любые два ребра u_im u_in Î U графа        G = (X, U), инцидентные одной и
той же вершине x_i Î X

Локальной
степенью (или просто степенью) вершины x_i графа G = (X, U) называется количество
рёбер ρ(x_i), инцидентных
данной вершине. Сумма локальных степеней всех
вершин графа G = (X, U) есть удвоенное количество
всех его рёбер:

                          (2)

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

ρ(x₁) = ρ(x₂) = … = ρ(x_n) = t.                                   

Количество
рёбер однородного графа степени t равно

                                               

Элементы графа

Подграф G‘ = (X‘, U‘) – это часть графа G = (X, U), если X‘ Í X, а множество U‘ Í U образовано всеми
рёбрами, соединяющими между собой только вершины из множества X΄.

Cуграф G‘ = (X‘, U‘) – это часть графа G = (X, U), если X‘ = X, U‘ Í U.

Кусок G_i = (X_i, U_i) – это часть
графа G = (X, U), если X_i Í X, U_i Í U, причём U_i=U_iiÈU_ij,

где U_ii – множество
рёбер, соединяющих вершины из множества X_i между собой; U_ij – множество
рёбер, соединяющих вершины из множества X_i с вершинами из множества
XX_i.

На
рис. 10 показан граф G = (X, U), а на рис. 11-13 – подграф, суграф и кусок этого графа
соответственно.

Если G_i = (X_i, U_i), i Î I = {1, 2, …, l) — части графа G = (X, U), причём, ,  , то
граф G можно определить
как объединение всех его частей G_i, т.е. .

Маршрут — это последовательность рёбер u_i Î U, заданных парами вершин
вида (x₁, x₂) (x₂, x₃) … (x_l-1, x_l), в которой
любые два соседних ребра смежные. Количество рёбер в маршруте определяет его
длину.

Если все рёбра в маршруте различны, то такой маршрут является
цепью.

Если в цепи нет повторяющихся вершин, кроме соседних, то
такая цепь называется простой.

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

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

Граф, представленный на рис. 1, содержит, например, маршрут

(x₁, x₃) (x₃, x₅) (x₅, x₂) (x₂, x₄) (x₄, x₁)                            

простую цепь

(x₁, x₃) (x₃, x₅) (x₅, x₂) (x₂, x₄)                                   

простой цикл

(x₁, x₃) (x₃, x₅) (x₅, x₂) (x₂, x₁)                                  

Две вершины x_i, x_j Î X, x_i ¹ x_j графа G = (X, U) называются связанными, если их можно
соединить маршрутом.

Граф G = (X, U) называется связным, если любые две его вершины связаны
маршрутом.

Если взять какую-либо вершину x_i Î X графа G = (X, U) и построить подмножество
X’ Í X, состоящее из всех
вершин, которые можно соединить с вершиной x_i произвольным маршрутом,
причём x_i включается в
множество X’, то подграф G’ = (X’, U’), образованный на
множестве вершин X’, называется компонентой связности графа G.

Связный
граф состоит из единственной компоненты связности. Если граф имеет несколько
компонент связности, то он несвязен, так как вершины из разных компонент
связности нельзя соединить маршрутом. На рис. 3.20, показан граф G = (X, U), состоящий из трёх
компонент связности G₁, G₂ и G₃, представленных на рис. 14-17

Связный
граф без циклов называется деревом. В дереве любые две вершины связаны
единственной цепью. Пример дерева показан на рис. 18.

Общее
количество деревьев d, которое можно построить на n вершинах, определяется по формуле

d = n^n-2      

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

Два графа G = (X, U) и G‘ = (X‘, U‘) называются изоморфными, если можно установить
следующее взаимнооднозначное соответствие X ↔ X‘,         U ↔ U’: если x_i, x_j Î X соответствует x‘_i, x‘_j Î X‘, то ребро (x_i, x_j) Î U соответствует (x‘_i, x‘_j) Î U‘. На рис. 19 и 20 показаны
изоморфные графы G и G‘. Вершинам x₁, x₂, x₃, x₄, x₅, x₆ поставлены во взаимное соответствие
вершины x‘₁, x‘₃, x‘₅, x‘₂, x‘₄, x‘₆.

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

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

Второй способ — метод соответствий (условное
название). Если задано множество вершин X и соответствие T, сопоставляющее каждой вершине x Î X графа множество вершин T_x, связанных с ней
рёбрами, то определён граф         G = (X, T). Для графа, представленного на рис. 1:

X = {x₁, x₂, x₃, x₄, x₅}.   T_x1 = {x₂, x₃, x₄, x₅};   T_x2 = {x₁, x₄, x₅};

T_x3 = {x₁, x₅};   T_x4 = {x₁, x₂}; T_x5 = {x₇, x₂, x₃}.

Третий
способ — матрица смежности графа R = || r_ij ||_n´n, где n — количество вершин
графа G, r_ij — элемент
матрицы смежности, расположенный на пересечении x_i строки и x_j столбца. Элемент
r_ij определяет
количество рёбер, инцидентных вершинам x_i и x_j. Если i = j, то элемент r_ij матрицы R определяет количество
петель при вершине x_i графа G. Для графа, представленного на   рис. 6, матрица
смежности будет иметь вид:

R =		x1	x2	x3	x4	x5
x1	0	1	5	0	2
x2	1	0	2	2	0
x3	5	2	0	2	0	(3)
x4	0	2	2	0	3
x5	2	0	0	3	0

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

Характеристические числа графов

Характеристические числа графов рассмотрим на примере
графа              G = (X, U) без петель и кратных рёбер.

Раскраска вершин графа — это такое разбиение множества его
вершин на p непересекающихся
подмножеств

X₁,
X₂, …, X_p, X = È X_i, X_i
Ç
X_j = Ø, i, j Î {1, 2, …, p},

в
котором каждое подмножество X_i не содержит смежных вершин.

Если каждому подмножеству X_i поставить в соответствие
определённую «краску», то вершины этого подмножества будут окрашены одинаковым
цветом, вершины другого подмножества X_j — другим и т.д., т.е.
вершины любой смежной пары окрашиваются в разные цвета.

Хроматическое число ξ(G) — это наименьшее
количество подмножеств, на которое можно разбить граф при раскраске.

Пример
1. Множество вершин X = {x₁, x₂, x₃, x₄, x₅, x₆} графа G (рис. 21) можно разбить не менее чем на
три непересекающихся подмножества: X₁ = {x₁, x₃, x₆}; X₂ = {x₂, x₄}; X₃ = {x₅}, т.е.  хроматическое число рассматриваемого
графа ξ(G) = 3, т.е.
вершины графа можно раскрасить красками тремя цветов.

Рис. 21

Предположим,
что граф G = (X, U) имеет n вершин, r рёбер и p компонент связности.
Наименьшее количество рёбер, после удаления которых в графе не содержится ни
одного цикла, называется цикломатическим числом γ(G). Цикломатическое
число определяется по формуле

γ(G) = r – n + p                                         
         (4)

Для графа G (рис. 1), у которого n = 6, r = 7, p = 1 цикломатическое число γ(G) = 7 – 6 + 1 = 2.

Цикломатическое число не может принимать отрицательные
значения.

Связный граф, у которого γ(G) = 0, является деревом, так как не
содержит ни одного цикла. 

Подмножество ψ_i Ì X графа G называется внутренне устойчивым, если любые две вершины
из этого подмножества не смежные.

В каждом графе без петель и кратных рёбер можно выделить
семейство всех внутренне устойчивых подмножеств: Ψ = {ψ₁, ψ₂, …, ψ_i}. Эти подмножества
различаются количеством входящих в них элементов.

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

η(G) = max | ψ_i |
                                          

Пример
2.  Граф, представленный на рис. 22, имеет:

Рис. 22

Ψ₁ = {x₁, x₄, x₆}; Ψ₂ = {x₂, x₅}; Ψ₃ = {x₂, x₆}; Ψ₄ = {x₃, x₄, x₆}; Ψ₅ = {x₄, x₅}.

Ψ_i = { Ψ₁, Ψ₂, Ψ₃, Ψ₄, Ψ₅}

Число
внутренней устойчивости η(G) = 3.

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

Ф =
{φ₁, φ₂, φ₃, φ₄}, φ₁ = {x₁, x₂, x₃}; φ₂
= {x₁, x₃, x₅}; φ₃
= {x₂, x₄}; φ₄
= {x₅, x₆},    а число внутренней
полноты χ(G) = max |φ_i| = 3.

Литература

1. Морозов, К.К. Методы разбиения схем РЭА на
конструктивно законченные части / К.К. Морозов, А.Н. Мелихов, Л.С. Бернштейн [и
др.] ; под ред. К.К. Морозова. – Москва : Сов. радио, 1978. С. 16-22.

2. Мелихов,
А.Н. Применение графов для проектирования дискретных устройств. / А.Н. Мелихов,
Л.С. Бернштейн, В.М. Курейчик – Москва : Наука, 1974. С. 40-43.

Не знаю как решить ? Можете сказать как можно решить эту задачу ?

По заданной матрице смежности неориентированного графа определите, содержит ли он петли.

Входные данные

В первой строке задано количество вершин n (1 ≤ n ≤ 100). Затем идут n строк по n элементов в каждой — описание матрицы смежности.
Выходные данные

Вывести «YES», если граф содержит петли, и «NO» в противном случае.

Входные данные #1

3
0 1 1
1 0 1
1 1 0

Выходные данные #1

NO

Входные данные #2

3
0 1 0
1 1 1
0 1 0

Выходные данные #2

YES