Что значит взвешенный граф

Что такое взвешенный граф в информатике

Вы будете перенаправлены на Автор24

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

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

Под взвешенным графом понимается граф, у которого рёбрам соответствуют некоторые весовые параметры. То есть каждому ребру (дуге) поставлено в соответствие некое числовое значение, которое называется длина дуги (или вес, стоимость). Обычные графы (не взвешенные) тоже возможно представить в виде взвешенных, если считать, что все их рёбра обладают весом равным единице. Под длиной пути во взвешенном графе понимается суммарная длина (вес) рёбер, составляющих данный путь. Расстоянием между вершинами считается дистанция самого короткого по весу пути. На рисунке один приведён пример взвешенного графа и там можно видеть, что расстояние между вершинами a и d равняется шести. То есть это путь с наименьшим суммарным весом (от вершины a и далее b, c, d).

graf1

Рисунок 1. Образец взвешенного графа. Автор24 — интернет-биржа студенческих работ

Эйлеровы и гамильтоновы графы

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

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

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

Готовые работы на аналогичную тему

graf2

Рисунок 2. Задача Эйлера о Кёнигсбергских мостах. Автор24 — интернет-биржа студенческих работ

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

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

Выяснив, что в этом графе нет циклических обходов, которые проходят по каждому ребру один раз, Эйлер решил поставить задачу в более общей формулировке: какие должны выполняться условия, чтобы такой цикл в графе мог быть обнаружен? Ответ на поставленный вопрос Эйлер дал в своей теореме. Теорема Эйлера: для существования в связанном неориентированном графе G эйлерова цикла, необходимо и достаточно, чтобы количество вершин с нечётной степенью не превышало две.

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

Источник

Теория графов. Часть третья (Представление графа с помощью матриц смежности, инцидентности и списков смежности)

Все, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор

Список смежности (инцидентности)

Взвешенный граф (коротко)

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

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

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

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

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

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

Смежность – понятие, используемое только в отношении двух ребер или в отношении двух вершин: два ребра инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Матрица (назовем ее L) состоит из n строк и n столбцов и поэтому занимает n^2 места.

Каждая ячейка матрицы равна либо 1, либо 0;

Ячейка в позиции L (i, j) равна 1 тогда и только тогда, когда существует ребро (E) между вершинами (V) i и j. Если у нас положение (j, i), то мы также сможем использовать данное правило. Из этого следует, что число единиц в матрице равно удвоенному числу ребер в графе. (если граф неориентированный). Если ребра между вершинами i и j не существует, то ставится 0.

Для практического примера возьмем самый обыкновенный неориентированный граф:

a348f8ee4003937d40b7c25b5e37cd28

А теперь представим его в виде матрицы:

c984671e2c427cd7ad51210cb86693b8

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

С одной стороны объем памяти будет:

f0606f1652446fa15f7f24acfee52e8b

Но используя вышеописанный подход получается:

757cba7e7f290ec83d8fbaeb05630572

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

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

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

Здесь отсутствует дублирование между вершинами, так как если вершина 1 соединена с вершиной 2, наоборот соединена она не может быть, так у нас есть направление у ребра.

Возьмем в этот раз ориентированный граф и сделаем матрицу смежности для него:

794659ca7186ff163f22cd03db5e7f1b

51f9d5e07ae0df17b23016d399330d6d

Если мы работаем со строкой матрицы, то мы имеем элемент из которого выходит ребро, в нашем случаи вершина 1 входит в вершину 2 и 8. Когда мы работаем со столбцом то мы рассматриваем те ребра, которые входят в данную вершину. В вершину 1 ничего не входит, значит матрица верна.

49a3aee249d3de1b63fb3ac623ef3bc1

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

Матрица инцидентности

Инцидентность – понятие, используемое только в отношении ребра и вершины: две вершины (или два ребра) инцидентными быть не могут.

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

Читайте также:  Чему бы ты хотел научиться в следующие 2 года

Ячейка в позиции I (i, j) равна 1 тогда, когда вершина инцидентна ребру иначе мы записываем в ячейку 0, такой вариант представления верен для неориентированного графа.

Сразу же иллюстрируем данное правило:

c2b7f47b72f4a6d8d796441561a0b789

c8e0df61c41db06f979ce45417389752

Сумма элементов i-ой строки равна степени вершины.

bda03c9394e75768b840eae72060d03b

47021e689aa7db8f6889de0b0137532f

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

4843c701e9ce3654e642a8dd4c2dd6bc

Список смежности (инцидентности)

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

af9cada20d55c80a42f36389b0c8bf2a

В виде списка это будет выглядеть так:

f14758f569048ec86d1d9fd4b6bcd7a1

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

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

3d39e49511ec04cda71daf896615dd70

37c4256696866a0b7aab99802cea245a

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

3f84ea7904128033ff5574743be38ad3

932f8b8d5c3e9eb19076fa7327f08663

Сумма длин всех списков:

212bc270ed5775339f8f1298c8af8f2a

013335811ed0ad5bc4d8013574f79160

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

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

Взвешенность графа

К примеру, возьмем граф с весами на ребрах:

2db3ff1cb3b2f1647c2214898c1b74ab

И сделаем матрицу смежности:

6e2b3e803927909cb1c91bd31990b699

В ячейках просто указываем веса ребра, а в местах где отсутствует связь пишем 0 или -∞.

Более подробно данное определение будет рассмотрено при нахождении поиска кратчайшего пути в графе.

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

Если заметили ошибку или есть предложения пишите в комментарии.

Источник

Погружение в графы

%D0%B8%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5 2021 08 12 230917

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

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

Прежде, чем познакомиться с направленным графом, взгляните на ненаправленный граф, представленный ниже:

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

Тут все меняется. Вы можете перемещаться между вершинами только в направлении стрелки, прикрепленной к каждому ребру. Например, вы можете перейти из пункта А в пункт В, но не из пункта В в пункт А. Немного более строго, верно?

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

Теперь подумаем о том, чтобы добавить веса ребрам графа. Представьте себе, что у каждого ребра есть цена; цена, которую нужно заплатить, чтобы пересечь ребро. Но перед этим представьте, что все ребра бесплатные, то есть имеют нулевую цену.

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

Хорошо, но что, если бы цены были другими? Как бы это изменило способ прохождения по графу?

Поскольку цены теперь отличаются друг от друга, вводится новая динамика. Переход от вершины к вершине будет стоить разных сумм “денег”. Иногда есть только один путь, но в некоторых случаях можно выбрать маршрут, и цена обычно служит определяющим фактором в этом решении. В общем, при переходе из одной вершины графа в другую “самый дешевый” путь является желаемым. Например, если бы я хотел выбрать самый дешевый путь из пункта А в пункт Е, я бы пошел по маршруту АBDЕ. Хотя первоначальным решением мог бы стать маршрут ABE, на самом деле он вышел бы дороже. Подсчеты показывают: стоимость ABE составляет 11, в то время как АBDЕ — всего 9. Надеюсь, вы получили основное представление о взвешенных графах.

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

Представление графов в коде

Итак, вы уже знаете, что такое направленные и взвешенные графы. Теперь выясним, как представить графы в коде. До сих пор мы использовали только иллюстрации графов. Что ж, оказывается, существует множество способов их представления в коде. Рассмотрим некоторые из них в отношении направленного и невзвешенного графа, показанного ранее.

Список ребер

Список ребер это именно то, на что похож приведенный ниже код; это список всех ребер на графе. Обратите внимание: каждое ребро представлено своими вершинами начальной и конечной.

Список смежности

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

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

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

В матрице смежности “0” означает, что две вершины не являются смежными, а “1”, указывает на то, что они являются смежными. Существует множество способов манипулировать такой матрицей и работать с ней, но это выходит за рамки данного объяснения. Обратите внимание на то, что на диагонали есть только нули. Подумайте, почему это так…

Для кодирования матрицы смежности существует несколько способов. В следующих случаях используется ООП:

Когда следует использовать каждый метод

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

Заключение

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

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

Источник

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

5fdb26f9c7693704931508

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

Читайте также:  Чем разжижать кровь при грудном вскармливании

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

В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.

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

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

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

Давайте на примере.

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

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

5fdb29509a644288566818

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

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

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

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

Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.

Пусть V — (непустое) множество вершин, элементы vV — вершины. Граф G = G(V) с множеством вершин V есть некоторое семейство пар вида: e = (a, b), где a, b ∈ V, указывающих, какие вершины остаются соединёнными. Каждая пара e = (a, b) — ребро графа. Множество U — множество ребер e графа. Вершины a и b — концевые точки ребра e.

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

Линейные структуры данных особенны тем, что связывают элементы отношениями по типу «простого соседства». Линейными структурами данных можно назвать массивы, таблицы, списки, очереди, стеки, строки. В нелинейных структурах данных элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порожденные и подобные.

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

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

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

Лемма о рукопожатиях

В любом графе сумма степеней всех вершин равна удвоенному числу ребер.

Доказательство леммы о рукопожатиях

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

Если же ребро является петлей — при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины).

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

Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные.

Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.

Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых.

Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3.

Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.

Путь и цепь в графе

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

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

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

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

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

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

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

5fdb29510e700334196189

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

Граф H, множество вершин V’ которого является подмножеством вершин V данного графа G и множество рёбер которого является подмножеством рёбер графа G соединяющими вершины из V’ называется подграфом графа G.

Визуализация графовых моделей

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

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

Граф можно нарисовать на плоскости или в трехмерном пространстве. Его можно изобразить целиком, частично или иерархически.

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

Виды изобразительных соглашений:

Виды графов

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

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

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

5fdb29926c89c057338196

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

5fdb29ba1044c254790639

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

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

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

Читайте также:  Чем приклеить пленку к стеклу окна

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

5fdb29ba54a64583798150

Пустой граф — это тот, что состоит только из голых вершин.

5fdb29ba61a40449143595

Мультиграфом — такой граф, в котором пары вершин соединены более, чем одним ребром. То есть есть кратные рёбра, но нет петель.

5fdb29ba70b01259021597

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

5fdb29ba8a854402094743

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

5fdb29db8c8dc592197891

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

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

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

5fdb29dbe59f7962738173

Эйлеров граф

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

Пример. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом?

5fdb29dc07694109831990

Регулярный граф

Регулярным графом называется связный граф, все вершины которого имеют одинаковую степень k.

Число вершин регулярного графа k-й степени не может быть меньше k + 1. У регулярного графа нечётной степени может быть лишь чётное число вершин.

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

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

5fdb29dc1cfcb822074272

Увеличим число вершин до восьми (следующее кратное четырем число). Соединим вершины ребрами так, чтобы степени вершин были равны трём. Получаем следующий граф, удовлетворяющий условиям задачи:

5fdb29dc2ec85079996596

Гамильтонов граф

Гамильтоновым графом называется граф, содержащий гамильтонов цикл.

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

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

5fdb29ff3f646171771292

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

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

5fdb29ff8420d732552657

Графы-деревья

Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом.

5fdb29ffa122b628754296

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

Определение дерева

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

Таким образом, в дереве невозможно вернуться в исходную вершину, перемещаясь по ребрам и не проходя по одному ребру два или более раз.

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

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

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

Дерево — минимальный по числу рёбер связный граф.

Висячей вершиной называется вершина, из которой выходит ровно одно ребро.

Определения дерева:

Очень часто в дереве выделяется одна вершина, которая называется корнем дерева. Дерево с выделенным корнем называют корневым или подвешенным деревом. Пример: генеалогическое дерево.

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

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

5fdb29ffadfc5800103676

Теоремы дерева и их доказательства

В дереве с более чем одной вершиной есть висячая вершина.

Доказательство первой теоремы:

Пойдем из какой-нибудь вершины по ребрам. Так как в дереве нет циклов, то мы не вернемся в вершину, в которой уже побывали. Если у каждой вершины степень больше 1, то найдется ребро, по которому можно уйти из неё после того, как мы пришли в нее.

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

В дереве число вершин на 1 больше числа ребер.

Доказательство второй теоремы:

Докажем по индукции по количеству вершин в дереве n. Если в дерево одна вершина, то факт верен. Предположим, что для всех n

У любого связного графа есть остовное дерево.

Доказательство третьей теоремы:

Чтобы найти остовное дерево графа G, можно найти цикл в графе G и выкинуть одно ребро цикла — потом повторить. И так пока в графе не останется циклов. Полученный граф будет связным, так как мы выкидывали рёбра, не нарушая связность, но в нём не будет циклов. Значит, он будет деревом.

Теория графов и современные прикладные задачи

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

Графы и задача о потоках

Система водопроводных труб в виде графа выглядит так:

5fdb29ffce90b403880027

Каждая дуга графа отображает трубу. Числа над дугами (весы) — пропускная способность труб. Узлы — места соединения труб. Вода течёт по трубам только в одном направлении. Узел S — источник воды, узел T — сток.

Задача: максимизировать объём воды, протекающей от источника к стоку.

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

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

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

Графы и сетевое планирование

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

PERT (Program (Project) Evaluation and Review Technique) — техника оценки и анализа программ (проектов), которую используют при управлении проектами.

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

Если в сети есть дуги (a, b) и (b, c), то работа, представленная дугой (a, b), должна быть завершена до начала выполнения работы, представленной дугой (b, c). Каждая вершина (vi) представляет момент времени, к которому должны быть завершены все работы, задаваемые дугами, оканчивающимися в вершине (vi).

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

Источник

Adblock
detector