Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 109808
17.11.2007, 09:36
0.00 руб.
0 1 1
Образование
8. Для данных графов выяснить, являются ли они изоморфными. Если да, то установить изоморфизм, в противном случае доказать, почему графы неизоморфны.
<img src=http://content.foto.mail.ru/mail/se.ju/1/i-3.jpg>

9. Дан граф G={V,E}, m(V)=8, m(E)=15. Требуется:
1. записать матрицу смежного графа;
2. установить является ли данный граф планарным, изобразить изоморфный ему плоский граф и записать для него формулу Эйлера;
3. если данный граф не является планарным, указать, какое из соотношений для плоских графов не выполняется.
<img src=http://content.foto.mail.ru/mail/se.ju/1/i-4.jpg>

10. Перераспределить заданный начальный поток по сети так, чтобы он стал максимальным, а сеть - насыщенной. Указать разрез, мощность которого равна величине максимального потока.
<img src=http://content.foto.mail.ru/mail/se.ju/1/i-5.jpg>

Обсуждение

Неизвестный
20.11.2007, 21:27
общий
это ответ
Здравствуйте, Ezhik!
8.
Эти графы изоморфны. Все три изображают полный двудольный граф K<sub>3,3</sub>.
Для установления изоморфности достаточно таким образом пронумеровать вершины (см. изображения во вложенном файле), чтобы вершины i и j были смежны тогда и только тогда, когда они смежны в остальных двух графах.

9.
а) матрица смежности графа:
(0 1 1 1 0 0 0 0)
(1 0 1 0 1 0 0 0)
(1 1 0 1 0 1 0 0)
(1 0 1 0 1 1 1 0)
(0 1 0 1 0 0 1 1)
(0 0 1 1 0 0 1 1)
(0 0 0 1 1 1 0 1)
(0 0 0 0 1 1 1 0)
Здесь на пересечении i-й строки и j-го столбца стоит 1 тогда и только тогда, когда i-я и j-я вершины соединены ребром.

б) Данный граф не планарный, т.к. он имеет более двух вершин нечётной степени: степени 1-й, 2-й и 8-й вершин равны трём, степень 4-й вершины равна пяти.
Форма ответа