Сколько вершин у графа изображенного слева
Перейти к содержимому

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

  • автор:

Подграфы — Теория графов

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

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

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

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

Индуцированные подграфы

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

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

Для наглядности посмотрим на графы ниже:

Здесь изображено три графа:

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

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

Ниже показан граф и два подграфа после удаления вершин:

  • Исходный граф
  • Подграф с удаленной вершиной — значит, мы должны удалить четыре ее ребра
  • Подграф с удаленными вершинами и — значит, мы должны удалить ребра с этими вершинами и в итоге разбить граф на две части

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

состоит только из одной вершины

, то вместо этого мы будем писать

. Если удаляем только одно ребро

Подграфы и клики

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

Посмотрим на примере:

На этом графе у нас есть две клики:

  • Из четырех вершин в левом нижнем углу (обозначена красным)
  • Из трех вершин в правом верхнем углу (обозначена зеленым)

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

Особенно часто клики упоминают в работе с циклами и путями в графах. Примеры пути и цикла в графе:

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

Независимое множество

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

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

Так независимое множество выглядит в графе:

Открыть доступ

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

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов

Наши выпускники работают в компаниях:

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Изображение Тото

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

Для перемещения по курсу нужно зарегистрироваться
1. Введение ↳ теория
2. Типы графов ↳ теория
3. Оптимизация маршрутов ↳ теория
4. Нотации ↳ теория
5. Подграфы ↳ теория
6. Связанность графов ↳ теория
7. Изоморфизм ↳ теория
8. Двудольные графы ↳ теория
9. Деревья ↳ теория
10. Остовные деревья ↳ теория
11. Взвешенный граф ↳ теория
12. Алгоритм Дейкстры ↳ теория
13. Эйлеровы схемы ↳ теория
14. Гамильтонов цикл ↳ теория
15. Доказательство гамильтонова цикла ↳ теория
16. NP-полнота ↳ теория
17. Раскрашивание графа ↳ теория
18. Диграфы ↳ теория
19. Связанность ↳ теория
20. Теорема Менгера ↳ теория
21. Поточная сеть ↳ теория

Поможем, если трудно

Порой обучение продвигается с трудом. Сложная теория, непонятные задания… Хочется бросить. Не сдавайтесь, все сложности можно преодолеть. Рассказываем, как

Не понятна формулировка, нашли опечатку?

Выделите текст, нажмите ctrl + enter и опишите проблему, затем отправьте нам. В течение нескольких дней мы улучшим формулировку или исправим опечатку

Что-то не получается в уроке?

Загляните в раздел «Обсуждение»:

  1. Изучите вопросы, которые задавали по уроку другие студенты — возможно, ответ на ваш уже есть
  2. Если вопросы остались, задайте свой. Расскажите, что непонятно или сложно, дайте ссылку на ваше решение. Обратите внимание — команда поддержки не отвечает на вопросы по коду, но поможет разобраться с заданием или выводом тестов
  3. Мы отвечаем на сообщения в течение 2-3 дней. К «Обсуждениям» могут подключаться и другие студенты. Возможно, получится решить вопрос быстрее!

Подробнее о том, как задавать вопросы по уроку

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

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

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

Задачи

1. Между девятью планетами Cолнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон — Меркурий, Меркурий — Венера, Уран — Нептун, Нептун — Сатурн, Сатурн — Юпитер, Юпитер — Марс и Марс — Уран. По каждому маршруту ракеты летают в обе стороны. Можно ли долететь на рейсовых ракетах от Земли до Марса?

Решение.
Построим граф, вершинами которого являются планеты Солнечной системы, а ребрами — существующие маршруты рейсовых ракет. Изобразив такой граф на рисунке, нетрудно заметить, что он состоит из двух компонент связности (на нашем рисунке они выделены разными цветами). Земля и Марс оказываются в разных компонентах связности, поэтому долететь от Земли до Марса на рейсоых ракетах нельзя.

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

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

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

Решение. Пронумеруем клетки поля 3×3, как показано на рисунке слева. Построим граф, вершинами которого являются эти клетки. Две клетки соединим ребром графа, если из одной в другую можно попасть за один ход коня. Расположим вершины графа так, как показано на рисунке справа, и проведем все ребра. Отметим на этом рисунке начальное и конечное местоположение коней. Для того, чтобы осуществить требуемую перестановку коней, нужно по крайней мере, чтобы, например, один из черных коней «перепрыгнул» через одного из белых. Но кони ходят по очереди, и ни в какой момент времени на одной клетке не могут оказаться два коня сразу. Поэтому осуществить такое «перепрыгивание» невозможно. Стало быть, невозможно и переставить коней требуемым образом.

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

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

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

5. В государстве 100 городов. Из каждого города выходит 4 дороги. Сколько всего дорог в государстве?

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

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

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

Решение. В качестве вершин графа возьмем телефоны, а в качестве ребер — телефонные провода. Применим к этому графу теорему 1. Степень каждой вершины графа равна 5, значит, сумма степеней всех вершин равна 5·15=75. Это нечетное число, поэтому его половина — число нецелое. То есть в нашем графе нецелое число ребер, и в городе нецелое число проводов, чего быть не может.

Следующую задачу в силу ее важности сформулируем в виде теоремы. 7. Теорема 2. Всякий (неориентированный) граф содержит четное число нечетных вершин.

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

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

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

Решение. Сделаем учеников вершинами графа, а ребрами будем соединять тех из них, которые дружат между собой. По условию в таком графе четных вершин будет 11, а нечетных 9+10=19, то есть нечетное число, что противоречит теореме 2.

9. Школьник Вася Пупкин сказал своему приятелю Вите Иванову:
— У нас в классе тридцать пять человек. И представь, каждый из них дружит ровно с одиннадцатью одноклассниками.
— Не может этого быть, — сразу же ответил Витя Иванов, победитель математической олимпиады.
Почему он так решил?

Решение. Решение этой задачи полностью аналогично решению задачи 6.
10. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?

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

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

Решение. Сделаем города вершинами графа, а дороги — его ребрами. По условию в этом графе 100 ребер, а по теореме 1 число ребер равно половине суммы степеней всех вершин. Значит, сумма степеней всех вершин равна 200. Но степень каждой вершины по условию равна 3, а 200 не делится на 3. Полученное противоречие доказывает, что такого быть не может.

12. В школе 953 ученика. Одни из них знакомы, другие не знакомы друг с другом. Доказать, что хотя бы у одного из них число знакомых среди учеников этой школы чётно.

Решение. Сделаем учеников вершинами графа и будем соединять ребрами тех из них, которые знакомы друг с другом. Если бы у всех школьников число знакомых среди учеников этой же школы число знакомых было нечетно, то все 953 вершины нашего графа были бы нечетными, что противоречит теореме 2. Значит, есть по крайней мере один школьник, у которого число знакомых среди учеников этой же школы четно. Более того, можно сказать, что таких школьников обязательно должно быть нечетное число (подумайте почему).

13. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

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

14*. Докажите, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4 и 2 соответственно.

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

15*. Можно ли расположить в пространстве 9 шаров так, чтобы каждый из них касался ровно пяти других?

Решение. Сделаем вершинами графа шары и соединим ребрами те из них, которые касаются друг друга. По условию в таком графе будет нечетное число нечетных вершин, что противоречит теореме 2.

16*. а) Можно ли нарисовать на плоскости 8 отрезков так, чтобы каждый пересекался ровно с тремя другими? б) Тот же вопрос для 9 отрезков.

Ответ. а) Да, см. рисунок; б) нет.

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

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!


Информатика и математика))))10-11 класс)))всё внутри!

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

(это задание с конкурса КИТ, по информатике. Мы сегодня писали а я не сделала это задание! Хочу всетаки понять какой тут ответ!)

Голосование за лучший ответ

Я вообще не могу понять причем тут математика и информатика какая то х*ня. 5?

Катька, смотри сколько концов свободных болтается.. . -их всего 4.
Это и есть твои «вершины со степенью 1».
Чтоб понять, двигаемся слева направо по картинке. Следи.
первая «вершина» (кружочек) сколько имеет связей? — ответ: одну (одной линией соединена с ещё одной «вершиной»-кружочком) .
Вторая (слева-направо, да? помнишь) верхняя «вершина» уже сколько имеет связей? Со сколькими кружочками связана? — ответ: с двумя. т. е. её степень =2. и т. д. (у третьей будет 4 связи, её степень — 4).
Всё на самом деле проще простого.

Похожие вопросы

Сети и графы

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

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

В работе [2] приводятся результаты о полном количестве (р, q) — графов с р вершинами и q ребрами и о количестве связных (р, q) — графов. Таблицы с небольшими значениями р и q приводятся многими авторами в публикациях. Приведенные здесь таблицы 1, 2 заимствованы из [2, стр.281]. Эти таблицы могут служить отправным пунктом для многих исследований сетей в различных предметных областях. Разработка новых методов получения результатов не только существования таких графов (числа графов), но перечислительного представления (желательно визуального) самих графов имеет несомненный интерес для практики и может служить прекрасной мотивировкой исследований. Дело в том, что даже в предлагаемой работе [2] перечисление графов в задачах ограничено и не доводится до визуальной формы (до изображений), а часто завершается получением производящих функций. Поэтому тем, кто стремится проводить глубокий анализ структур сетей, необходим для такого анализа (и возможно синтеза) перечень конкретных графов (их рисунков), что позволяет привлекать когнитивные способности человеческого мозга к поиску наилучших решений.

Таблица 1 – Число (р, q) — графов

символом р обозначено число вершин, символом q – число ребер

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

Таблица 2 – Число связных (р, q) -графов

символом р обозначено число вершин, символом q – число ребер

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

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

Определение графа. Обыкновенный граф G (V, U) порядка n представляет собой конечное непустое множество V, содержащее n = |V| вершин, и множество U неупорядоченных пар U ≤ V×V из р = |U| различных вершин (vi, vj); при таком определении автоматически исключаются петли при вершинах и параллельные (кратные) между парами вершин ребра. Пара вершин uij = (vi, vj), соединенных отрезком линии и принадлежащая множеству U, называется ребром графа G и говорят, что ребро uij соединяет вершины vi и vj. Вершины vi и vj называются при этом смежными.

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

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

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

Хорошая классификация должно обладать свойством предсказания, обеспечивать прогнозы, выполнение расчетов, например, объемов классов, перечисление его элементов и свойств. В публикации предлагается такой набор свойств: количество вершин, количество ребер, распределение степеней вершин (РСВ), изоморфизм. Примером класса (Табл. 6) в этой классификации могут быть: 6-вершинники с 8 ребрами, фиксированным РСВ 123334>, неизоморфные графы.

Подобная классификация просто описывается деревом с 4-мя ярусами: 1-й вершины, 2-й ребра, 3-й РСВ, 4-й изоморфизм. Решение прикладных задач с использованием классов в рамках подобной классификации предусматривает привлечение разнообразного математического инструментария: комбинаторного анализа сочетаний, разбиений числа, установления (проверки) изоморфизма графов, включаемых в конкретный класс.

Свойства графов и их элементов

Инцидентность. Пара вершин vi, vj являющихся оконечными в ребре uij = (vi, vj), называются инцидентными ребру, а ребро – инцидентным каждой из этих вершин.

Степень вершины. Каждой вершине vi графа с номером i, i = 1(1) n, инцидентно di ребер di = 0(1) n – 1. Переменная (величина) di называется степенью вершины графа. Множество вершин графа описывается характеристикой D = d1, d2, d3, …, dn> – распределение степеней вершин (РСВ). Число вершин в графе, имеющих нечетные степени – четно, а сумма степеней всех вершин графа равна удвоенному количеству ребер Dσ = i≤ndi = 2р.

Главный подход (цель) при классификации – собрать в классы объекты с одинаковыми наборами, но с разными значениями показателей свойств. Визуально графы легко различаются значениями: n = |V| – количеством вершин, р = |U| – количеством ребер, di – значениями степеней вершины ( количеством ребер, сходящихся в одной i-й вершине ) и вектором D = d1, d2, d3, …, dn> – распределением степеней вершин (РСВ) графа. Это существенно упрощает контроль принадлежности графа классу.

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

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

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

Для конечных графов соответствующее количество разбиений также конечно, но среди их множества не все будут отвечать требованиям РСВ графа. Для разбиений чисел вводится понятие «графическое разбиение». Выбором из полного множества разбиений (табл.4) только «графических», получаем из таких разбиений множество допустимых РСВ. Ниже в числовом примере 1 будет показан механизм такого выбора.

Пример. Ниже в таблице 6 приводится множество графов, образующих класс G (6, 8). В этом классе можно увидеть и выделить подкласс G (6, 8, D), где D =.d1, d2, d3, …, d6>=1,2,3,3,3,4>. Подкласс образуют графы с номерами G9, G10, G11, G13

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

Некоторые типы матриц для графа

матрицы смежности и инцидентности для графа на рис. 2, также перестановочная матрица g

Генерация графов заданного класса

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

Структура обыкновенного графа определяется количествами (n) элементов (вершин) и (р) связей этих элементов (ребер), а также пространственным размещением связей между парами вершин, что определяется РСВ. Связи в неориентированном графе называются ребрами (в ориентированном графе – дугами). Каждая связь соединяет пару вершин. При n вершинах количество ребер (р) в полном графе вычисляется как число комбинаторных сочетаний по два из n вершин р = n(n – 1)/2

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

Рисунок 1 - Полный пятивершинник и соотношения для вычислений

В этой ситуации в ряде классов G (n, p, D) графы с одинаковыми D, n и р оказываются разными. Их структуры не совпадают (не совмещаются) при наложении графов одного на другой. Другими словами, существует признак, который делает графы, принадлежащие классу, а, следовательно, и структуры разными. Этот признак скорее качественный, чем количественный и называется изоморфизм. Разные по структуре графы – неизоморфны.

При известных числах вершин (n) и ребер (p) в классе G (n, p), его объем определяется как число сочетаний из числа ребер в полном n-вершиннике по заданному числу р ребер моделируемого класса.

Пример 1. Для класса обыкновенных графов G (n, p) = G (5, 7) получить множество всех графов. Необходимо генерировать для 5-вершинников все семиреберники. Решение этой задачи возможно несколькими путями, зависящими от формы представления графов: рисунками, сочетаниями, матрицами или как-то иначе. Выберем представление графа сочетанием ребер. Полный обыкновенный 5-вершинный граф (рис. 1) содержит р =10 ребер, но в задаче требуются 7-реберные графы, ребра которых должны связывать пары из 5 вершин и создавать разные структуры, следовательно, в полном графе необходимо для получения 7-реберника убрать 3 ребра. В класс попадает столько графов, сколько существует различных вариантов убрать три ребра из десяти.

Предварительно в полном 5-вершиннике пронумеруем позиции всех его десяти ребер (рисунок 1 полный 5-вершинник). Тогда каждому очередному графу сочетание из списка (табл. 3) укажет в какие позиции полного графа должны укладываться 7 заданных ребер. Таких сочетаний (следовательно, и структур графов) существует 120.

С другой стороны, для сочетаний справедливы 120 соотношений, из которых следует, что для получения семиреберников с 5 вершинами из полного 5-вершинника можно удалять 3 ребра. Для этого необходимо генерировать сочетания по три ребра из 10, и получаемые в списке сочетаний тройки с номерами ребер удалять из полного графа.

Таблица 3 – Нумерованные сочетания из 10 ребер по 3, которые удаляются из полного графа, чтобы получить все 5-вершинные 7-реберники

В клетках за двоеточием записаны номера удаляемых ребер полного 5-вершинника

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

Изоморфизм графов. Два графа А и В с матрицами смежности n × n, называются изоморфными (обозначается А≈ В) тогда и только тогда, когда существует g-матрица (подстановочная) порядка n, соответствующая подстановке g ϵ Sn , для которой выполняется g А g -1 = В. Здесь g и g -1 прямая и обратная подстановочные матрицы порядка n × n. Для всех матриц А (G(n, p)) смежности графа в классе G(n, p) вводится понятие «старшинство» матриц.

Любую (0, 1) -матрицу можно представить двоичным числом, выписывая последовательно ее строки одну за другой с 1-й до n-й. Эту (0, 1) -последовательность прочитывают как двоичное число. Для двух сравниваемых матриц старшей будет та, для которой число больше. Для симметрических матриц смежности графа можно (при преобразовании ее в число) ограничиться верхней треугольной частью. Наибольшее число старшей матрицы в классе называется кодом Харари матрицы.

Если при действии на А любой g-матрицей из симметрической группы Sn подстановок степени n ее старшинство в линейно-упорядоченном множестве матриц не возрастает, т.е. для любой g ϵSn, g А g -1 ≤ А, то А – каноническая матрица. Очевидно, две различные канонические матрицы смежности графов соответствуют неизоморфным графам.

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

Рисунок 2 -При получении 5-вершинников с одной вершиной степени di = 2 (РСВ D =2 3 3 3 3>) из полного графа необходимо удалять три ребра: пару ребер инцидентных этой вершине и третье ребро, не инцидентное трем вершинам, удаляемых ребер. В полном графе с каждой вершиной инцидентны 4 ребра из чего следует шесть возможностей удаления двух из них 4(4 – 1)/2 = 6.

Другими словами, с каждой вершиной связаны 6 изоморфных графов, а вершин в графе 5, следовательно, получаем 6×5 = 30 изоморфных графов, в которых одна из вершин имеет степень два. Рисунок 2 поясняет приводимые рассуждения. Пятая вершина имеет степень два (d5 = 2), удалены два инцидентных ребра с номерами 4 и 9. Этим двум ребрам инцидентны три вершины v5, v1, v3 не инцидентное ребро связывает другие вершины v2, v4. Оно будет третьим удаляемым ребром.

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

6-вершинники с 6-ю ребрами и РСВ вида D = 2, 2, 2, 2, 2, 2>; пара графов: один граф цикл (кольцо), содержащий все вершины, другой – два треугольника;

8-вершинники с 8-ю ребрами и РСВ вида D = 2,2,2,2,2,2,2,2>, аналогично цикл (кольцо) или два четырехугольника. Наложение пар таких графов одного на другой покажет несовпадение их структур, т.е. пары графов неизоморфны. Второй граф в паре несвязен.

Рисунок 3 - Пары неизоморфных графов в классах G (n, p, D)

Граф (полный) 6-вершинник имеет 15 ребер. Мы рассматриваем два 6-вершинных 6-реберника: один граф – кольцо и второй – несвязный 6-вершинник – два треугольника. В полном списке графов 6-вершинников с шестью ребрами (их существует 5005) кольцо имеет код сочетания 1,5,6,10,13,15 и порядковый номер № 1613, а пары несвязных треугольников, например, с кодами 4, 5, 15, 6, 7, 10 и 1,2,6,12,13,15 получают соответственно № 4099 и № 587.

Разбиения числа. Как определить и задать РСВ графов? Степени вершин графа удобно описывать разбиениями четного числа (удвоенного числа ребер) на n блоков. Среди множества разбиений (табл.4) будут встречаться такие, которые представляют РСВ графов из классов с заданными количествами вершин и ребер. Степень di любой вершины обыкновенного графа G (V, P) не может превышать di ≤ n – 1 их число в графе.

Пример 3. Для класса G (5, 7) все возможные РСВ, содержащиеся в списке разбиений числа 14 на 5 частей помещены в таблице 4 ниже.

Таблица 4 – нумерованные разбиения четного числа 14 на 5 частей

5-вершинники с 7 ребрами и заданным разбиением удвоенного числа ребер, среди которых (с номерами 18, 21-23) являются распределением степеней сершин

Все разбиения подразделяются на графические и неграфические. Неграфическими разбиениями являются, содержащие блоки со значением n = 5 и более. Такие блоки не могут быть компонентами РСВ 5-вершинника. В таблице выше это разбиения с номерами: 1 – 11, 13 –16, 19, 20.

Следовательно, проверке разбиения на возможность стать РСВ должны подвергаться только разбиения с номерами: 12, 17, 18, 21–23. Построить графы с номерами компонентов РСВ 12 и 17 невозможно, поэтому остаются допустимыми только четыре РСВ: 18, 21–23, соответствующие неизоморфным графам.

. Рисунок 4 – Пятивершинные графы с 7-ю ребрами и объемы классов

Связность графа

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

Так в примере 2 задаются две пары графов: в первой паре оба графа имеют число (n = 6) вершин и число (p = 6) ребер графа равными, одинаковы у них и РСВ 222222> – распределение степеней вершин (РСВ), во второй паре графы также имеют число (n = 8) вершин и число (p = 8) ребер графа равными, одинаковы у них и РСВ 22222222> – распределение степеней вершин (РСВ), но вторые графы в этих парах генерируемых графов – несвязные (рис.3).

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

Определение. Вершинной связностью τ = τ(G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Это вершинная связность.

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

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

Алгоритмы установления (проверки) связности графа

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

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

– минимальная степень (d) вершин в графе;

– минимальное число ребер (рmin), образующих сечение в графе;

– минимальное число вершин (umin), образующих сечение в графе, что соответствует гарантированному числу вершинно-независимых путей, связывающих произвольную пару вершин в графе;

– число деревьев (корневых) содержащихся в графе.

Для вероятностных графов в качестве показателей связности называются следующие:

– вероятность связности графа;

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

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

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

Это свойство следует из того, что если в графе выбрать пару вершин, которые наиболее удалены одна от другой и, «потянуть» за вершины в противоположные стороны, то все ребра цепи, связывающей эту пару вершин, выстроятся в одну линию. Очевидно, самая длинная цепь в графе, возникает тогда, когда она содержит все n его вершин, при этом она будет состоять из n – 1 ребра.

Пример 4. Задан размеченный граф (8-вершинник) с 16 ребрами (рис. 5). В нем выбрана пара не смежных вершин v = 3, v = 8. Результат эластичного растяжения графа и его ребер изображен на (рис. 5). Вершины v = 3, v = 8 связаны цепью, содержащей все остальные вершины графа и n – 1 ребро, следовательно, граф является связным.

Матричный алгоритм установления связности. Другое свойство графа связано с матрицей смежности А[n] графа. Если матрицу графа последовательно возводить в степень k, k = 2(1)(n – 1), то элементы последовательно получаемых матриц описывают для соответствующих пар вершин число связывающих их цепей «длины» k, которая измеряется числом ребер.

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

Для связного графа матрица С[n] (n – 1) = 1[n]+ к А к [n] не содержит нулевых элементов. Если это не так, то граф, для которого определена матрица С[n] не является связным. Таким образом, алгоритм определения С[n] (n – 1) позволяет установить факт связности (несвязности) графа.

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

Таблица 5 Нумерованные разбиения четного числа 16 на 6 частей

6-вершинники с 8 ребрами и заданным разбиением удвоенного числа ребер, среди которых разбиения (с номерами 13-15, 18, 20-23, 26-30, 32-35) являются распределением степеней вершин

Метод использует матрицу смежности А[n] рассматриваемого графа. Если пара (vi, vj) вершин соединена ребром, то элемент матрицы аij = 1, если нет, то аij = 0. Подсчитывается количество единиц в каждой строке и подставляют эти значения вместо нулей на главной диагонали в той же строке. Все единицы, не лежащие на главной диагонали, заменяют на (–1). Теперь при отбрасывании любой вершины i, т. е. вычеркивания i-х строки и столбца получаем матрицу В[n-1]. Вычисляя значение определителя матрицы В[n–1] определяем является ли граф связным или нет.

Если detВ[n-1] >0, то граф является связным, если detВ[n-1]0, то граф не является связным. Этот алгоритм подробно описан в работе [1] и использован автором при вычислениях. Завершая изложение публикации, приведем пример построения всех (22 графа )связных графов класса G(6, 8), представляемых матрицами смежности и изображениями в одинаковом порядке. Над каждым изображаемым графом выписаны векторы D – распределения степеней его вершин.

Таблица 6 Матричное представление нумерованных графов класса G (6, 8). Объем класса 22 графа, что можно увидеть в таблице 2.

Матричные представления графов класса G (6, 8).

Визуальные изображения графов класса G (6, 8) с указанием для каждого из них РСВ

Визуальные изображения графов класса G (6, 8).

Заключение. Пришло время ответить на вопрос, поставленный в задаче в начале текста. Как выбрать лучшую структуру для сети? Обратимся к рисунку 4. На нем представлен класс графов G(5,7) – это всего 4 изображения связных 5-вершинников с 7 ребрами. Из этих 4-х структур предстоит сделать выбор лучшей структуры для сети в смысле надежности ее функционирования в условиях возмущающих воздействий. Эти воздействия могут приводить к отказам линий связи: одной или более с вычисляемой вероятностью. Левая конфигурация отклоняется при выборе лучшей сразу, так как при ее выборе и отказе одной линии связи связь с вершиной 1 будет утрачена.

Сложнее ситуация, допускающая отказ двух связей. Наш пример подобран так, что и в этом случае ответ будет однозначным – это правая структура рисунка. Шанс утратить связь с одной из вершин при отказе двух линий в этой структуре наименьший из трех остающихся потенциально возможных для выбора структур. Дело в том, что в правой структуре имеется единственная вершина степени d = 2 и именно эта единственная вершина связана с остальными менее надежно. Слева от правой структуры расположена структура, имеющая две вершины со степенью два, а левее этой структуры расположена структура, имеющая три вершины степени два. Как видим шансы структуры остаться связной при отказе двух линий у этих трех структур различны. Поэтому выбор однозначен лучшая – это правая структура.

Литература

1. Авондо-Бодино Дж. Применение в экономике теории графов – М.: Прогресс,1966. –160с. 2. Харари Ф., Палмер Перечислительные задачи комбинаторного анализа. – М.: Мир, 1979. – 364 с.
3. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *