Сколько циклов в полном графе

Простейшие понятие о графах. Представления графов в памяти, классические алгоритмы.

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

История возникновения теории графов

Леонард Эйлер и задача о Кёнигсберских мостах

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

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

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).

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

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

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

Проблема четырёх красок

Проблема четырёх красок — математическая задача, предложенная Гутри в 1852 году.

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

Иначе говоря, показать что хроматическое число плоского графа не превосходит 4.

О доказательстве

К. Аппель и В. Хакен доказали в 1976 г., что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница), впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок. Проблема четырех красок является одним из известнейших прецедентов неклассического доказательства в современной математике.

Определения теории графов

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

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

Пример ориентированного графа

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

Пример: граф с шестью вершинами и семью рёбрами

Граф, в котором каждая пара вершин соединена ребром, называется полным. Обозначение: K_n – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n–угольник, в котором проведены все диагонали.

Ниже приведены полные графы с числом вершин от 1 до 8 и количества их рёбер.

K1 : 0	K2 : 1	K3 : 3	K4 : 6
K5 : 10	K6 : 15	K7 : 21	K8 : 28

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

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

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

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

Понятия плоского графа и грани графа применяется при решении задач на «правильное» раскрашивание различных карт.

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

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

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

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

Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B.

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

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

Если не выделять особым образом корень, то дерево — это просто любой связный граф, не имеющий циклов

Представление графов в памяти

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

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

Самый простой способ сохранить граф в памяти — матрица смежности. Нарисуем таблицу, которая чем-то напоминает таблицу умножения: в первой строчке и в первом столбце будут стоять номера (или любые названия) вершин, а на пересечении столбца и строки будем ставить, например, 1 если между этими вершинами есть ребро и 0 если нет. Кроме 1 и 0 можно ставить, например, вес ребра, а для обозначения отсутствия ребра — просто очень большое число. Какой именно вариант использовать, зависит от каждой конкретной задачи. Также задача определяет, что ставить на диагонали получившейся матрицы.

Теперь достаточно запустить обход из стартовой вершины. Например, так: dfs(0) .

Обход в ширину (BFS)

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

Этот обход, как и обход DFS, можно применять для поиска путей в графах. Основное его отличие в том, что поиск не уходит сразу далеко от начала, а продвигается вглубь графа постепенно, неким «фронтом».

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

Поиск кратчайших путей

Очень часто требуется найти кратчайший путь между двумя вершинами во взвешенном графе. Очевидный пример — прокладка маршрута по карте. Для решения этой задачи существует большое количество алгоритмов, в числе которых алгоритм Флойда и алгоритм Дейкстры. Алгоритм Флойда является самым простым, но очень неоптимальным — его сложность $O(n^3)$. Алгоритм Дейкстры быстрее ($O(n^2)$ или $O(n \log n)$, в зависимости от реализации), но имеет некоторые ограничения.

Рассмотрим самый простой алгоритм поиска пути — алгоритм Флойда. Его преимущества состоят в том, что он реализуется очень легко, может работать с рёбрами отрицательного веса и одновременно находит кратчайшие пути между всеми парами вершин. Алгоритм Флойда — один из немногих алгоритмов, которые лучше работают с матрицей смежности, чем со списками рёбер. Алгоритм последовательно изменяет матрицу смежности, превращая её в матрицу кратчайших путей — в каждой клетке матрицы остаётся длина (сумма весов) кратчайшего пути между соответствующей парой вершин. Условие работы алгоритма — если между какой-то парой вершинам нет ребра, в исходной матрице смежности в этой клетке должна стоять «бесконечность», обычно это число, заведомо больше весов всех рёбер в данной задаче.

Алгоритм устроен так: для каждой вершины графа, пусть её номер будет $k$, просматриваются все пары вершин, пусть это $i$ и $j$. Если сумма текущей известной длины пути из $i$ в $k$ и из $k$ в $j$ меньше, чем из $i$ в $j$, то в клетке, соответствующей пути из $i$ в $j$, запоминаем длину пути через $k$, иначе ничего делать не требуется. Таким образом, алгоритм содержит три вложенных цикла, поэтому его сложность — $O(n^3)$.

Посмотрим, как реализовать этот алгоритм на Python:

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

Алгоритм Дейкстры будет рассматриваться на зимней очной сессии.

Другие задачи

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

Сколько циклов в полном графе

e mptyhope → World Tour Finals 2022 Predictions
Pyqe → COMPFEST 15 Preliminary — Editorial
sword060 → [Tutorial] Persistent DSU made trivial
BlueSmoke → Codeforces Round #641 Editorial
P etr → AWTF22 arrival
Zlobober → Разбор VK Cup 2015 — Finals
KyoumaHououin → Help Needed for CSES — Palindrome Queries
Ibrahim-Elsayed → [Help] How to solve this problem?
AkibAzmain → Feature Request: Allow blocking a blog from appearing in the "Recent Actions" section for me
coderdhanraj → CF New Chrome Extension (Userscript): CF Get Problems
CodemastersIntl → До окончания регистрации на Codemasters Code Cup осталось 5 дней
hetanhnandre → How to improve ?
CodeChef_admin → Invitation to September 2023 Short (Unrated for all) — 6th Sept
SashaT9 → SashaT9 Contest 1
peltorator → Round numbering system
vrooooom → USACO Bronze/Silver Classes Offered by CPI for Fall 2023!
Aliyyiakbar → Why Am I Struggling in Competitive Programming?
__fn__ → Tricks and help for improving
Na2Na2 → If you're reading this you have been IP logged
Eslam_Ahmed → Support My Team to participate in the ACPC Championship!
adamant → C++ STL: Policy based data structures
Parisa_Amiri → Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)
dweenHex → new comers problem
Medeali → Advice on efficient practice
yashsaha555 → Modulo

Блог пользователя ruslan.rakhimov

Поиск всех циклов в графе

Автор ruslan.rakhimov, 9 лет назад ,

При изучении алгоритма на e-maxx Проверка графа на ацикличность и нахождение цикла понял, что алгоритм прекращает работу при нахождении первого цикла. Как найти все циклы в графе? Я переделал исходный алгоритм. При реализации моего алгоритма, некоторые циклы упускаются из вида. Например:

Ребра в неориент. графе: 1 2 1 3 2 3 2 4 3 4 Циклы: 1 2 3 1 2 3 4 2 1 2 4 3 1

Мой алгоритм find_cycles() не находит третий цикл. Как можно это исправить?

поиск в глубину, цикл, граф
Комментарии (8)

Все циклы — это все простые циклы? (Если нет, то их обычно бесконечно много.)

В полном графе из n вершин различных простых циклов — порядка n!. Так что в любом случае решение, работающее для произвольного графа, будет не быстрее перебора. Перебор отличается от поиска в глубину тем, что при выходе из рекурсивной функции следует вообще снимать пометку ( color[v] = 0; ).

При выходе она у меня снимается же? ( color[v] = 2; )

Вообще снимать — это вернуть в исходное состояние. Чтобы if(color[to] == 0) не отличил.

Циклов в графе может быть порядка O(N N ) . Вы все еще хотите их искать? 🙂

Значит для задач это бысмысленное дело? Т.е. в задачах это не нужно?

Иногда бывает нужно. Gassa выше уже сказал, как можно найти все простые циклы.

Интересно, что можно "быстро" найти базис "простых циклов".

Или формально: сопоставим циклу битовую строку длинной E (число ребер), ясно, что сумма таких битовых строк даст битовую строку, соответствующую циркуляции. То есть можно найти базис в лин. пространстве циркуляций. Таким базисом будет следующий набор циклов: строим остовный лес, далее берем любое ребро не из леса, и получаем, отбросив ненужную часть леса, цикл. Несложно заметить, что это базис. таким образом размеренность пространства: E-(V-C), C-число компонент связности.

← Rev. 2 → -13

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

Оценка количества простых циклов на графе

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

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

Формализация задачи

Итак, для определенности будем рассматривать граф G – ориентированный, без петель.

При этом порядок графа равен, очевидно, N, а количество рёбер – M.

Графу можно взаимно однозначно сопоставить матрицу смежности A.

Вследствие ориентированности графа G соответствующая матрица смежности в общем случае асимметрична:

Условие (4) отсутствия петель в графе приводит к тому, что на главной диагонали матрицы смежности допустимы только нулевые элементы

и матрица, таким образом, имеет вид

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

Будем далее обозначать

Оценка количества циклов

Для построения оценочной формулы примем следующее допущение: для графа G нам известны только порядок графа и количество рёбер в нём; точный вид матрицы смежности, какие-либо закономерности её формирования и т.п. нам неизвестны. Другими словами, мы будем считать, что наш конкретный граф был сконструирован в результате стохастического процесса такого рода:

Были зафиксированы N вершин графа, т.е. множество V.

Матрица смежности размером N x N была заполнена нулевыми значениями.

В матрице смежности совершенно случайным образом были выбраны ровно M элементов, не лежащих на главной диагонали, и им были присвоены единичные значения.

На указанных вершинах в соответствии с матрицей смежности были построены ребра графа E.

С учётом изложенного и (11), вероятность того, что произвольный элемент матрицы смежности вне главной диагонали равен единице, очевидно, равна

Легко увидеть, что выражения (12), (13) определяют циклическое размещение без повторений длины K из генеральной совокупности V размером в N элементов; из комбинаторики известно, что количество различных размещений при этом составляет

Для того, чтобы циклическое размещение из (12), (13) соответствовало циклу на графе G, необходимо, чтобы выполнялись условия (14), (15), т.е. чтобы существовали соответствующие рёбра, или, другими словами, K соответствующих элементов матрицы смежности были равны единице. С учётом (18), вероятность этого составляет

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

Заметим, что теперь количество циклов длины K на графе можно рассматривать как случайную величину, математическое ожидание которой из (19) и (21) составляет

И, наконец, математическое ожидание количества циклов на графе G с учётом (17) равно

Это и есть искомая оценка.

Замечания и обсуждение

Прежде всего, заметим, что указанная оценка довольно неплохо согласуется с экспериментальными данными. В таблице 1 приведены данные о количестве циклов в графах, полученные переборным методом. Эксперимент охватывал 4 группы графов, в каждой группе содержалось по 10 графов с 50-ю вершинами каждый и количеством рёбер 90, 100, 110 и 120 для каждой из групп соответственно. Несмотря на то, что для каждого конкретного графа количество циклов может заметно отличаться от оценочного, среднее по группе значение достаточно близко к нему.

Далее, стоит отметить, что даже для сравнительно небольших графов оценка (23) предсказывает наличие весьма значительного количества циклов на них; ряд оценочных значений приведен в таблице 2. Это стоит учитывать при планировании вычислений, связанных с перебором циклов на графе: они могут занять несколько больше времени и ресурсов, чем кажется!

Ещё одним интересным моментом является то, что формула (23) позволяет легко построить функцию, которую можно интерпретировать как оценку плотности распределения циклов по длинам:

На рис. 1 изображены графики оценочной и экспериментальной плотности распределения циклов по длинам на графе с 60 вершинами и 140 рёбрами. Как видно, они довольно неплохо согласуются между собой. При этом под экспериментальной плотностью понимается

где количества циклов в отношении получены прямым подсчётом.

Таким образом, оценка (24) позволяет сделать вполне обоснованное предсказание о характерных длинах циклов на графе.

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

Заключение

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

Теория графов – Типы графов

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

Нулевой график

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

пример

На приведенном выше графике есть три вершины с именами «a», «b» и «c», но среди них нет ребер. Следовательно, это нулевой граф.

Тривиальный график

Граф с единственной вершиной называется тривиальным графом .

пример

На приведенном выше графике есть только одна вершина «а» без других ребер. Следовательно, это тривиальный граф.

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

Ненаправленный граф содержит ребра, но ребра не являются ориентированными.

пример

В этом графе «a», «b», «c», «d», «e», «f», «g» – вершины, а «ab», «bc», «cd», «da». ‘,’ ag ‘,’ gf ‘,’ ef ‘- ребра графа. Поскольку это ненаправленный граф, ребра «ab» и «ba» совпадают. Точно так же другие ребра также рассматриваются аналогичным образом.

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

В ориентированном графе каждое ребро имеет направление.

пример

На приведенном выше графике у нас есть семь вершин «a», «b», «c», «d», «e», «f» и «g», и восемь ребер «ab», «cb», « dc ‘,’ ad ‘,’ ec ‘,’ fe ‘,’ gf ‘и’ ga ‘. Поскольку это ориентированный граф, на каждом ребре есть метка стрелки, показывающая его направление. Обратите внимание, что в ориентированном графе «ab» отличается от «ba».

Простой график

Граф без петель и параллельных ребер называется простым графом.

Максимально возможное число ребер в одном графе с n вершинами равно n C _2, где n C ₂ = n (n – 1) / 2.

Число простых графов возможно с n вершинами = 2 n c ₂ = 2 n (n-1) / 2 .

Максимально возможное число ребер в одном графе с n вершинами равно n C _2, где n C ₂ = n (n – 1) / 2.

Число простых графов возможно с n вершинами = 2 n c ₂ = 2 n (n-1) / 2 .

пример

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

Максимальное количество ребер с n = 3 вершинами –

Максимальное количество простых графов с n = 3 вершинами –

Эти 8 графиков, как показано ниже –

Связанный график

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

пример

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

Отключенный график

Граф G несвязен, если он не содержит хотя бы двух связанных вершин.

Пример 1

Следующий график является примером отключенного графа, где есть два компонента, один с вершинами «a», «b», «c», «d», а другой с «e», «f», «g», ‘h’ вершины.

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

Пример 2

В этом примере есть два независимых компонента, abfe и cd, которые не связаны друг с другом. Следовательно, это несвязный граф.

Обычный график

Граф G называется регулярным, если все его вершины имеют одинаковую степень . В графе, если степень каждой вершины равна «k», то этот граф называется «k-регулярным графом».

пример

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

В обоих графах все вершины имеют степень 2. Они называются 2-регулярными графами.

Полный график

Простой граф с «n» взаимными вершинами называется полным графом и обозначается «K _n » . В графе вершина должна иметь ребра со всеми остальными вершинами, тогда она называется полным графом.

Другими словами, если вершина связана со всеми остальными вершинами графа, то она называется полным графом.

пример

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

Цикл графика

Простой граф с n вершинами (n> = 3) и ребрами n называется графом циклов, если все его ребра образуют цикл длины n.

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

пример

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

Граф I имеет 3 вершины с 3 ребрами, которые образуют цикл ‘ab-bc-ca’.

Граф II имеет 4 вершины с 4 ребрами, которые образуют цикл ‘pq-qs-sr-rp’.

Граф III имеет 5 вершин с 5 ребрами, которые образуют цикл ‘ik-km-ml-lj-ji’.

Граф I имеет 3 вершины с 3 ребрами, которые образуют цикл ‘ab-bc-ca’.

Граф II имеет 4 вершины с 4 ребрами, которые образуют цикл ‘pq-qs-sr-rp’.

Граф III имеет 5 вершин с 5 ребрами, которые образуют цикл ‘ik-km-ml-lj-ji’.

Следовательно, все данные графы являются графами циклов.

Колесо График

Граф колеса получается из графа циклов C _n-1 путем добавления новой вершины. Эта новая вершина называется Hub, которая связана со всеми вершинами C _n .

пример

Посмотрите на следующие графики. Они все колесные графики.

На графике I он получен из C ₃ путем добавления вершины в середине, названной ‘d’. Обозначается как W ₄ .

На графике II он получен из C ₄ путем добавления вершины в середине, названной ‘t’. Обозначается как W ₅ .

На графике III он получен из C ₆ путем добавления вершины в середине, названной ‘o’. Обозначается как W ₇ .

Циклический график

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

пример

В приведенном выше примере графа у нас есть два цикла abcda и cfgec. Следовательно, он называется циклическим графом.

Ациклический Граф

Граф без циклов называется ациклическим графом.

пример

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

Двудольный график

Простой граф G = (V, E) с разбиением вершин V = 1 , V ₂ > называется двудольным графом, если каждое ребро E соединяет вершину в V ₁ с вершиной в V ₂ .

В общем случае бипертитовый граф имеет два набора вершин, скажем, V ₁ и V ₂ , и если ребро нарисовано, он должен соединить любую вершину в наборе V ₁ с любой вершиной в наборе V ₂ .

пример

На этом графике вы можете наблюдать два набора вершин – V ₁ и V ₂ . Здесь два ребра с именами «ae» и «bd» соединяют вершины двух множеств V ₁ и V _2.

Полный двудольный график

Двудольный граф ‘G’, G = (V, E) с разбиением V = 1 , V ₂ > называется полным двудольным графом, если каждая вершина в V ₁ соединена с каждой вершиной V ₂ .

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

пример

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

Если | V ₁ | = m и | V ₂ | = n, то полный двудольный граф обозначается через K _{m, n} .

K _{m, n} имеет (m + n) вершин и (mn) ребер.

K _{m, n} регулярный граф, если m = n.

K _{m, n} имеет (m + n) вершин и (mn) ребер.

K _{m, n} регулярный граф, если m = n.

В общем случае полный двудольный граф не является полным графом .

K _{m, n} полный граф, если m = n = 1.

Максимальное число ребер в двудольном графе с n вершинами

Если n = 10, k5, 5 = ⌊ n 2/4 ⌋ = ⌊ 10 2/4 ⌋ = 25

Аналогично К6, 4 = 24

Если n = 9, k5, 4 = ⌊ n 2/4 ⌋ = ⌊ 9 2/4 ⌋ = 20

Аналогично К6, 3 = 18

«G» является двудольным графом, если в «G» нет циклов нечетной длины. Частным случаем двудольного графа является звездный граф .

Звездный График

Полный двудольный граф вида K _{1, n-1} является графом звезд с n-вершинами. Звездный граф является полным двудольным графом, если одна вершина принадлежит одному набору, а все остальные вершины принадлежат другому набору.

пример

На приведенных выше графиках из n вершин все n – 1 вершины связаны с одной вершиной. Следовательно, оно имеет вид K _{1, n-1,} которые являются графами звезд.

Дополнение графика

Пусть ‘ G – ‘ – простой граф с некоторыми вершинами, такими как у G, и ребро присутствует в ‘ G – ‘ , если ребро отсутствует в G. Это означает, что две вершины смежны в « G – », если две вершины не смежны в G.

Если ребра, которые существуют в графе I, отсутствуют в другом графе II, и если граф I и граф II объединены вместе, чтобы сформировать полный граф, то граф I и граф II называются дополнениями друг друга.

пример

В следующем примере graph-I имеет два ребра: «cd» и «bd». Его граф дополнения II имеет четыре ребра.

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

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

Если «G» – простой граф, то

| E (G) | + | E ( ‘ G – ‘ ) | = | E (K _n ) |, где n = количество вершин в графе.

пример

Пусть ‘G’ – простой граф с девятью вершинами и двенадцатью ребрами, найдите число ребер в ‘ G – ‘ .

У вас есть, | E (G) | + | E ( ‘ G – ‘ ) | = | E (K _n ) |

12 + | E ( ‘ G – ‘ ) | знак равно

12 + | E ( ‘ G – ‘ ) | = 36

«G» – простой граф с 40 ребрами, а его дополнение « G – » имеет 38 ребер. Найдите количество вершин в графе G или ‘ G – ‘ .

Пусть количество вершин в графе равно n.

Имеем, | E (G) | + | E ( ‘ G – ‘ ) | = | E (K _n ) |