Вес ребра графа это

Содержание урока

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

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

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

ur 13 06

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

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

ur 13 07

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

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

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

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

ur 13 08

Следующая страница smotri 1Оптимальный путь в графе

Cкачать материалы урока
skachat

Источник

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

Содержание

Ориентированные графы [ править ]

Определение:
Конечным графом (англ. finite graph) [math]G[/math] называется граф, в котором множества [math]V[/math] и [math]E[/math] — конечны. Следует заметить, что большинство рассматриваевых нами графов — конечны.
Определение:
Изоморфные графы (англ. isomorphic graphs) — два графа [math]A[/math] и [math]B[/math] называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им рёбрами.

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

Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,

Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).

Источник

Лекция 11. Графы

Геометрические графы

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

1. каждая замкнутая кривая множества image007 содержит только одну точку множества image006;

2. каждая незамкнутая кривая множества image007 содержит ровно две точки множества image006, которые являются ее граничными точками;

3. кривые множества image007 не имеют общих точек, за исключением точек из множества image006.

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

Очевидно, что вершины любого абстрактного графа можно представить точками пространства, а его ребра отождествить с некоторыми простыми кривыми, соединяющими концы этих ребер. Поэтому любой абстрактный граф всегда эквивалентен (по отношению к свойствам, изучаемым в теории графов) некоторому геометрическому графу. Геометрический граф, эквивалентный в указанном выше смысле абстрактному графу, будем называть изображением этого абстрактного графа. Таким образом, геометрические графы можно рассматривать как удобное и наглядное представление абстрактных графов, а не просто как частный случай. Отметим только, что существует огромное количество вариантов расположения вершин геометрического графа в пространстве и не меньшее количество способов начертания его ребер. Следовательно, у абстрактного графа могут быть различные по виду изображения, на первый взгляд совершенно не похожие друг на друга. Оба графа на рис.4.1 являются изображениями абстрактного графа из примера 4.1. Не похожи и три изображения абстрактного графа, показанные на рис. 4.2.

image052

image053Кстати, граф image054 на рис.4.2 представляет собой неориентированный дубликат орграфа (рис. 4.3).

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

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

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

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

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

Определение 4.4. Графы, вершинам и (или) ребрам которых приписаны некоторые веса, называют взвешенными графами. Графы, вершины которых пронумерованы, еще называют помеченными графами.

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

Степени вершин

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

Число image057, равное числу звеньев, соединяющих вершины image013 и image014, назовем кратностью этих вершин. Если у графа нет кратных звеньев, то image058 или image059, при этом у неориентированных графов image060.

У графа, представленного на рис. 4.4, image061=1 (висячая вершина), image062=0 (изолированная вершина) и image063=2, если считать петлю однократным звеном. При этом image064image065, а image066image067image068.

Выпишем несколько простых формул. Очевидно, что степень любой вершины графа image013 равна сумме кратностей всех пар вершин image013, image014:

image069.

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

image070.

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

image071.

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

Это утверждение установлено Эйлером и является исторически первой теоремой теории графов.

Источник

Теория Графов. Часть 1 Введение и классификация графов

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

Введение

Сначала под землей города Москвы ничего не было. Потом была построена первая станция метро, а затем и вторая и третья. Образовалось множество станций метро. На карту было занесено множество точек. Позже между станциями стали прокладывать пути линии. И соединилась станция метро А со станцией метро Б. Все остальные станции также стали соединятся друг с другом и на карте появилось множество линий. В итоге мы имеем Московский метрополитен очень красивый, я там был проверял.

image loaderСхема Московского метро

Посмотрите какая красота. У нас имеется множество точек (которые называются вершинами или узлами), а также множество линий (называемые рёбрами или дугами). Обозначим множество вершин буквой V от английского vertex−вершина и множество рёбер обозначим E от английского edge−ребро. Граф в формулах именуют буквой G. Все вершины обязательно должны быть идентифицированы.

Отмечу, что число вершин обозначается буквой n:

image loader

Число рёбер обозначается буквой m:

image loader

Таким образом граф задается и обозначается парой V,E:

4c01ffe7992f18620e67fbe6558127d4

Также определение графа рассказывается в этой статье на Хабре (https://habr.com/ru/post/65367/)

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

Разберем определение графа подробней. Может ли в G быть пустым множество E? Да без проблем! Такой граф будет называться нулевым, а вершины в нем будут называться изолированными.

image loaderНулевой граф

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

Множество E задается парой неупорядоченных вершин множества V.

Пример: Пусть множество V = <1,2,3,4,5>. Тогда множество E =

Граф будет выглядеть следующим образом:

image loader

Висячей вершиной называется вершина которая соединена только с одной соседней вершиной. В нашем случаи висячей вершиной будет вершина 5, так как она соединена только с вершиной 1.

Степень записывают, как:

00ef890366b0090e640a6d6c03371b82

Максимальная степень, то есть какое количество степеней вообще присутствуют в графе обозначаются, как:

6d60f3d3cc2bee8fecd7e52b502db72c

cded565a6ca3bd4db422d0fc60afe00e

Формула суммы степеней для G = V,E выглядит так:

image loader

То есть сумма степеней всех вершин v графа равна удвоенному количеству его рёбер E. Считаем количество степеней в нашем примере. От этого никуда не денешься. Я насчитал 12. А теперь считаем, сколько у нас рёбер. Их 6! Умножаем на 2 и получаем 12. Совпадение? Не думаю!

А давайте представим наш граф в другом виде, но с сохранением данных пар. G теперь имеет следующий вид:

image loader

Заметьте я не изменил пары между собой. Вершина 4 также соединяется с вершиной 3, а у вершины 1 степень также осталась 4. Так почему граф имеет совершенно другой вид и законно ли это?

Классификации графов

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

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

image loaderНеориентированный граф

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

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

Также существует граф со смешанными ребрами. Это когда в графе присутствуют, как ориентированные рёбра, так и неориентированные.

image loaderСмешанный граф

Вторым признаком является отсутствие или наличие кратных ребер.

image loaderМультиграф

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

Заключение

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

Источник

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

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

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

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

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

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

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

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

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

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

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

Матрица (назовем ее 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. То есть она может быть, как квадратной, так и отличной от нее.

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

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

c2b7f47b72f4a6d8d796441561a0b789

c8e0df61c41db06f979ce45417389752

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

bda03c9394e75768b840eae72060d03b

47021e689aa7db8f6889de0b0137532f

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

4843c701e9ce3654e642a8dd4c2dd6bc

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

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

af9cada20d55c80a42f36389b0c8bf2a

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

f14758f569048ec86d1d9fd4b6bcd7a1

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

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

3d39e49511ec04cda71daf896615dd70

37c4256696866a0b7aab99802cea245a

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

3f84ea7904128033ff5574743be38ad3

932f8b8d5c3e9eb19076fa7327f08663

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

212bc270ed5775339f8f1298c8af8f2a

013335811ed0ad5bc4d8013574f79160

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

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

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

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

2db3ff1cb3b2f1647c2214898c1b74ab

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

6e2b3e803927909cb1c91bd31990b699

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

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

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

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

Источник

Adblock
detector