Вершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф



Дата02.01.2013
Размер21.4 Kb.
ТипЗанятие
Занятие 3. Вершинная и реберная связность графов. Расстояния в графе.

Изоморфизм графов. Разрезы в графе.

26. Докажите неравенство , где - вершинная связность графа G, - реберная связность, - минимальная степень вершины графа.

27. Найдите радиус, диаметр и центр

а) графа G из задачи 23; б) графа Н4 из задачи 31.

28. Докажите, что для любого графа G .

29. Докажите, что для каждого графа G, содержащего цикл, справедливо неравенство: , где - длина наименьшего цикла в графе G.

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

31. Изоморфны ли данные графы? Ответ обоснуйте.







а) G1 G2







б) H1 H2







в) G3 G4





г) H3 H4

32. Исследуйте данные тройки графов на попарную изоморфность.






png" name="object18" align=bottom width=105 height=103>
а) G1 G2 G3









б) Н1 Н2 Н3







в) G4 G5 G6

33. Пусть связные графы G и H имеют по 6 вершин и по 8 ребер. У графа G ровно 2 вершины степени 2, а граф Н имеет ровно 4 вершины степени 3. Можно ли утверждать, что графы G и H

а) изоморфны? б) не изоморфны?

34. Сколько существует попарно неизоморфных графов с
а) 16 вершинами и 118 ребрами? б) 16 вершинами и 117 ребрами?

3

5.
Найти минимальный разрез и цикломатический набор ребер в следующих графах:



G: H:



Похожие:

Вершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Вершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф iconПрограмма вступительного экзамена в аспирантуру по специальностям 05. 13. 05 "Элементы и устройства вычислительной техники и систем управления"
Комбинаторика и Комбинаторные объекты. Методы комбинаторного анализа. Теория графов. Основные понятия и определения. Способы задания...
Вершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф iconБилеты по Дискретной математике «Теория Графов»
Понятие графа (орграфа). Смежность и инцидентность в графе. Классы (типы) графов
Вершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф iconТема: Связность графов. Множества сочленения и разделяющие множества
В теории графов, понятие связности графа является ключевым при решении многих прикладных задач
Вершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф iconОсновные понятия теории графов граф и его виды
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик...
Вершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф iconНаучная работа по теме: 1 глава 1 4 теория графов 4 Эйлеровы графы 7 Задача о мостах, Леонард Эйлер и теория графов 8
Как это сделать? Я стала искать пути решения, и оказалось, что это можно сделать с помощью графов. Раньше понятием «граф» я встречалась...
Вершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф iconКак показано в § 4, среди графов с фиксированными порядком и числом компонент лишь один имеет максимальное число ребер. Другой крайний случай минимальное число ребер приводит к большому классу графов
Доказано, например, что все деревья ре­конструируемы; несложно распознается изоморфизм деревьев. С другой стороны, деревья часто...
Вершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф iconАлгоритм Зыкова
Определение графа. Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Локальная степень. Подграф. Полный...
Вершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф iconРабочая программа дисциплины "Теория конечных графов и ее приложения" Направление подготовки 010300. 62 «фиит»
Графы ориентированные и неориентированные. Изоморфизм графов. Маршруты, цепи, циклы. Деревья. Помеченные графы. Плоские и планарные...
Вершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org