Сколько вершин у графа изображенного слева

Сколько вершин и рёбер у графа, представленного на рисунке?

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

ОБОСОБЛЕННЫЕ ЧЛЕНЫ ПРЕДЛОЖЕНИЯ

Запишите предложения, выделяя обособленные члены предложения (в скобках укажите – что обособленно: приложение, обстоятельство, согласованное или несогласованное определение):

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

2. Приглядевшись внимательнее, Костя увидел бюст Льва Толстого.

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

4. Над крышей гордо возносился конёк – стилизованная голова лошади.

5. Отличить полезный, «настоящий» труд от мартышкиного просто: ощущаешь себя молодцом, завершив работу, или понимаешь, что занялся не своим делом.

6. Делая усилия, мы становимся частью этого пространства.

7. Впереди были горы, высокие, неприступные.

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

9. А он, сообразительный малыш, уже знает, что делать: жуёт конфету, берёт мою скрипку и начинает играть мой урок.

10. Заворожённый этим зрелищем и заколдованный своим малодушием, я замер.

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

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

Знакомство с ГРАФАМИ

Информация для учителей, работающих в матемаческих кружках.

Просмотр содержимого документа
«Знакомство с ГРАФАМИ»

Знакомьтесь: граф

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

Пример 1. В деревне 9 домов. Известно, что у Петра соседи Иван и Антон, Максим сосед Ивану и Сергею, Виктор – Диме и Никите, Евгений – сосед Никиты, а больше соседей в этой деревне нет (соседними считаются дворы, у которых есть общий участок забора). Может ли Пётр огородами пробраться к Никите за яблоками?

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

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

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

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

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

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

Кстати, с дворянским титулом «граф» их связывает общее происхождение от латинского слова «графио» — пишу.

Замечания:

1. Каждое ребро соединяет ровно две вершины.

2. Вершины, из которых не исходит ни одного ребра, называются изолированными.

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

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

Такие одинаковые, но, быть может, по-разному нарисованные графы принято называть изоморфными. На рисунках 3а и 3б изображены изоморфные графы.

Определение 2. Степенью (или порядком) вершины называется количество рёбер, исходящих из этой вершины. Вершина называется чётной, если из неё выходит чётное число рёбер, и нечётной, если из неё выходит нечётное число рёбер.

Так, например, в графе, изображенном на рисунке 3, первая и пятая вершины имеют степень 1, вторая вершина – степень 4, третья и четвертая вершины – степень 2.

Пример 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединён с пятью другими?

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

Пример 4. На концерте каждую песню исполняли двое артистов, и никакая пара не выступала вместе более одного раза. Всего было 12 артистов, каждый выступил по 5 раз. Сколько было песен?

Решение. Рассмотрим граф, вершинами которого являются выступавшие артисты. Соединим пару артистов ребром, если они вместе пели. Получим граф с 12 вершинами степени 5, каждой песне соответствует ребро. Аналогично предыдущему примеру, в графе рёбер, то есть было 30 песен.

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

Замечания:

5. Чтобы подсчитать число рёбер графа нужно просуммировать степени вершин и полученный результат разделить на два.

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

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

Решение. Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 – степень 4, 10 – степень 5. Однако сумма степеней вершин такого графа нечётна (проверьте), что противоречит замечанию 6. Не может.

Определение 3. Путём в графе от вершины А до вершины В называется последовательность рёбер графа, в которой два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза, А – начало пути, В – конец.

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

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

Пример 6. Сколько рёбер в полном графе с пятью вершинами?

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

Определение 7. Граф называется связным, если для любой его вершины найдется путь, связывающий её с любой другой вершиной этого графа.

На рис. 1 мы видим, что граф несвязен, на рис. 2, 3, 4 изображены связные графы, кроме того они имеют циклы.

Замечания:

7. Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. (Например, на рис. 1 две компоненты связанности, то есть изображён один граф соседства, состоящий из двух «кусков»).

8. Связный граф имеет одну компоненту связности.

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

Пример 7. В тридевятом царстве лишь один вид транспорта – ковёр-самолёт. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных – по 20. Докажите, что из столицы можно долететь в город Дальний (возможно с пересадками).

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

Докажем методом «от противного». Пусть в компоненте связности города Дальнего нет. Тогда в ней из одной вершины выходит 21 ребро, а из всех остальных – по 20. То есть сумма степеней вершин нечётна, что противоречит замечанию 9. Получили противоречие, значит наше предположение неверно, то есть город Дальний входит в эту же компоненту связности.

Пример 8. Можно ли нарисовать графы, изображенные на рис. 5а и на рис. 5б, не отрывая карандаш от бумаги и проводя каждое ребро один раз?

Решение. а) Можно. Например, последовательность вершин может быть такой: 1-2-3-1-4-2-5-3-4.

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

Возможно, вам знакома аналогичная задача про открытый конверт (или домик).

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

Замечание:

10. Эйлеров граф должен иметь не более двух нечётных вершин.

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

Пример 9. Схема мостов Кёнигсберга изображена на рис. 6. Можно ли совершить прогулку, пройдя по каждому мосту ровно один раз?

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

Пример 10. В углах шахматной доски 3 3 стоят 4 коня: 2 белых (в соседних углах) и два чёрных (см. рис. 7а). Можно ли за несколько ходов (по шахматным правилам) поставить коней так, чтобы во всех соседних углах стояли кони разного цвета?

Решение. Отметим центры клеток доски и соединим отрезками пары отмеченных точек, если из одной в другую можно перейти шагом коня (конь ходит буквой Г). Мы получили граф (см. рис. 7б). В нём есть изолированная вершина (см. замечание 2), это вершина 5. Попробуйте обойти все остальные вершины графа и вернуться в исходную вершину. У вас должно получиться, ведь рёбра и все вершины, кроме вершины 5, образуют эйлеров граф, содержащий цикл. Перемещение коней по доске соответствует движению по рёбрам этого цикла. Для графа на рис. 7б изображен изоморфный граф (см. рис. 7в и замечание 4). Ясно, что при движении по циклу нельзя изменить порядок следования коней.

Список литературы (советуем почитать):

1. Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки: пособие для внеклассной работы. Глава 6. Графы–1. Киров: АСА, 1994 г.

2. Гуровиц В.М., Ховрина В.В. Графы. Москва: МЦНМО, 2012 г.

3. Каннель-Белов А.Я., Ковальджи А.К. Как решают нестандартные задачи. Часть I. Идеи и методы решения задач: Графы. Москва: МЦНМО, 2008 г.

4. Савин А. Графы. Журнал «Квант» № 6, 1994 г.

5. Фосс В. Элементы теории графов. Журнал «Квант» № 8, 1973 г.

8.1. В стране Цифра есть девять городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Два города соединены авиалинией только в том случае, если двузначное число, составленное из цифр-названий этих городов, делиться на 3. Можно ли добраться из города 1 в город 9?

8.2. В фирме 50 компьютеров, некоторые пары компьютеров должны быть соединены кабелями. От каждого компьютера должно отходить по 8 кабелей. Сколько понадобиться кабелей?

8.3. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

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

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

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

Сколько вершин у графа изображенного слева

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

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

Задачи

3. Можно ли, сделав несколько ходов конями из исходного положения (верхний рисунок), расположить их так, как показано на нижнем рисунке? (Выходить за пределы поля 3×3 не разрешается.)

Построим граф, вершинами которого являются города, а ребрами — существующие авиалинии. Вспомним признак делимости на 3: натуральное число делится нацело на 3 тогда и только тогда, когда сумма его цифр делится на 3. Заметим, что если название города делится на 3, то он соединен авиалиниями только с городами, названия которых тоже делятся на 3. Наоборот, те города, названия которых не делятся на 3, не могут быть соединены авиалиниями с городами, названия которых делятся на 3. Поэтому города 3, 6 и 9 образуют одну компненту связности графа, в которую никакие другие города не входят. Это означает, что из города 1 в город 9 добраться по воздуху нельзя.

Упражнение: А какие еще компоненты связности есть в этом графе?

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

6. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
Подсказка: попытайтесь посчитать количество телефонных проводов.

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

8. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 — по 4 друга, а 10 — по 5 друзей?

Дискретная математика / Графы

Теория графов — тот редкий раздел математики, о котором доподлинно известно, когда он родился и кто был его осново­положником. Родилась теория графов в Санкт-Петербурге. Ее создателем является Л. Эйлер, который в 1736 году опубликовал решение задачи о Кенигсбергских мостах. Суть задачи состоит в следующем. Город Кенигсберг был построен в месте слияния двух рек на их берегах и на двух островах. В нем было семь мостов, которые соединяли острова между собой и с береговыми частями города. Мог ли любой житель города выйти из дома, пройти по всем семи мостам в точности по одному разу и вер­нуться домой?

На рис. 1 плана города a, b, c, d — части суши. Эйлер дал отрицательный ответ на поставленный вопрос. Более того, он доказал, что подобный маршрут имеется только для такого гра­фа, каждая из вершин которого связана с четным числом ребер (на графе, изображенном на рисунке справа, части суши изобра­жены точками — вершинами графа, а связи между ними — линиями произвольной конфигурации, называемыми ребрами или дугами).

Рис. 1. План города Кенигсберга и граф к задаче о Кенигсбергских мостах

Теорию графов нача­ли разрабатывать для решения некоторых задач о геомет­рических конфигурациях, состоящих из точек и линий. В этих задачах несущественно, соединены ли точки конфи­гурации отрезками прямых или криволинейными дугами, какова длина линий и другие геометрические характеристи­ки конфигурации. Важно лишь то, что каждая линия соеди­няет какие-либо две из заданных точек. Таким образом, можно дать определение графа как совокупности двух мно­жеств V (точек) и U (линий), между элементами которых определено отношение инцидентности, причем каждый эле­мент uU инцидентен ровно двум элементам v’, v». Элементы множества V называются вершинами графа G, элементы множества U — его ребрами. Вершины и ребра графа G называют еще его элементами и вместо vV, uU пишут соответственно v G и uG.

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

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

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

На рис.2,а – з изображены не­которые неориентированные графы. Множество ребер U может быть пустым (рис. 2,г). Если же множество вершин V пусто, то пусто и U. Такой граф называется пустым. Линии, изображающие ребра графа, могут пересекаться, но точки пересечения не являются вершинами (рис.1,д); различ­ные ребра могут быть инцидентны одной и той же паре вер­шин (рис. 2, е), в этом случае они называются кратными; граф, содержащий кратные ребра, часто называют мультиграфом. Ребро может соединять некоторую вершину саму с собой (рис. 2,ж), такое ребро называется петлей. На рис. 2,з изображен фрагмент бесконечного графа. Его вершины — это точки плоскости с целыми координатами (х, у), а ребра — соединяющие их горизонтальные и верти­кальные отрезки длины 1.

Обычно рассматриваемые графы конечны, т. е. конечны множества их элементов (вершин и ребер).

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

Степенью вершины называется число дуг, инцидентных ей. Вершина степени 1 называется висячей(рис. 3, ж, в). Вершина степени 0 называется изолированной(рис. 3, б).

Маршрутом в G называется такая конечная или бесконеч­ная последовательность ребер, что каж­дые два соседних ребра имеют общую инцидент­ную вершину. Одно и то же ребро может встречаться в маршруте несколько раз.

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

Рис. 4. Пример цепей и циклов в графе: (l2, l5, l6) — цепь; (l1, l2, l5) — простая цепь; (l2, l3, l4, l5) — цикл; (l2, l4, l5) — простой цикл.

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

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

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

Подграфом Gа графа G = < V, U > называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с ребрами (дугами), их соединяющими. Так, карта шоссейных дорог Пермской области является подграфом графа «Карта шоссейных дорог Российской Федера­ции».

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

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

Рис.5. Граф – дерево

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

Простейшее дерево состоит из двух вершин, соединенных ребром. Каждый раз, когда добавляется еще одно ребро, в конце его прибавляется также и вершина. Следовательно, дерево с n вершинами имеет n — 1 ребро.

В теории графов доказывается, что число различных деревьев, которые можно построить на m вершинах, равно m m -2 . Много де­ревьев — это лес.

Цикломатическое число. Пусть G — неориентированный связный граф, имеющий n вершин и m ребер. Цикломатическим числом связного графа G с n вершинами и m ребрами называется число:

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

Рассмотрим примеры подсчета числа независимых циклов.

В графе, состоящем из одной вершины и одного ребра, один цикл (рис. 6, а).

В графе, состоящем из одной вершины и трех ребер, три цик­ла (рис. 6, б).

В графе, состоящем из двух вершин и двух ребер, один цикл (рис. 6, в).

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

В графе, состоящем из трех вершин и трех ребер, один цикл (рис. 6, д).

В графе, состоящем из трех вершин и четырех ребер, два цик­ла (рис. 6, е).

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

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

В графе, состоящем из четырех вершин и шести ребер, три цикла (рис. 6, и).

Цикломатическое число дерева равно нулю.

Рис.6. Примеры циклов в графах:

а, в, д, ж — один цикл; б, и — три цикла; г — четыре цикла; е, з — два цикла

Хроматическое число графа. Граф G называют р-хроматическим, где р — натуральное чис­ло, если его вершины можно раскрасить р-различными цветами так, чтобы никакие две смежные вершины не были раскрашены одинаково. Наименьшее число р, при котором граф является р-хроматическим, называют хроматическим числом графа и обоз­начают λ(G). Если λ (G) = 2, то граф называют бихроматическим. Необходимым и достаточным условием бихроматичности явля­ется отсутствие в графе циклов нечетной длины.

Граф на рис. 7, а — бихроматический, его вершины «раскра­шены» двумя «цветами», обозначенными 0,1.

Рис. 7. Примеры раскраски графов: а — бихроматический граф; б — граф, раскрашенный тремя цветами

Граф на рис. 7, б можно «раскрасить» тремя цветами, напри­мер, черным (ч), красным (к) и белым (б).

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

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

Матрицей смежности ориентированного поме­ченного графа с n вершинами называется матрица А= [a_ij], где i, j= 1, 2. n, в которой a_ij = 1, если существует ребро (х_i, ,х_j) или 0, если вершины х_i, ,х_j не связаны ребром (х_i, ,х_j).

Матрица смежности однозначно определяет структуру графа. Примеры орграфа и его матрицы смежности приведены соответ­ственно на рис. 8 и рис. 9. Отметим, что петля в матрице смежности может быть представлена соответствующим единич­ным диагональным элементом. Кратные ребра можно предста­вить, позволив элементу матрицы быть больше 1, но это не при­нято, обычно же представляют каждый элемент матрицы одним двоичным разрядом.

Рис. 8. Ориентированный граф

Рис.9. Матрица смежности ориентированного графа рис.8

Матрица инцидентности графа. Матрицей инцидентности для неориентированного графа с n вершинами и m ребрами называется матрица В= [b_ij], i = 1, 2. n, j= 1, 2…m, строки которой соответству­ют вершинам, а столбцы — ребрам. Элементы b_ij = 1, если вершина х_i, инцидентна ребру u_j или b_ij = 0, если вершина x_i не инцидентна ребру u_j.

Пример графа и его матрицы инцидентности с 5 вершинами и 7 ребрами представлен на рис. 10 и рис.11 соответственно.

Рис.10. Ориентированный граф

Рис. 11. Матрица инцидентности графа рис.10

Список ребер графа. При описании графа списком его ребер каждое ребро пред­ставляется парой инцидентных ему вершин. Это представление можно реализовать двумя массивами r= (r₁, r₂, . r_m) и t= (t₁, t₂, . t_m), где m — количество ребер в графе. Каждый элемент в массиве есть метка вершины, а i-е ребро графа выходит из вершины r_i, и входит в вершину t_i. Например, соответствующие массивы пред­ставления графа на рис. 8 будут иметь вид: