Математическое моделирование на графах. Часть 1. Берцун В.Н. - 57 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Глава 2. Плоские и планарные графы 57
G
n–1
в множестве G(n – 1), если к нему добавить новую вершину и
соединить ее со старыми вершинами нечетной степени. Поэтому
|Э'(n)| ≤ |G(n – 1)|. C другой стороны, число графов с n вершинами
определяется через количество ребер в полном графе
|G(n)| = 2
q
, q = C(n, 2) = n(n – 1)/2.
Учитывая, что C(k,2)-C(k – 1, 2) = k – 1,
получим
|Э(n)| ≤ |Э'(n)| ≤ |G(n – 1)| = 2
C(n–1, 2)
= 2
c(n, 2) – (n–1)
= |G(n)|·2
– (n–1)
.
Тогда δ = |Э(n)| / |G(n)|
1
1
2
n−
≤ и δ→0 при n→∞,
т.е. почти нет эйлеровых графов. ■
Эйлеров цикл в эйлеровом графе можно найти, если нумеровать
ребра по алгоритму Флери [24]:
- выбираем произвольную вершину а и одно из инцидентных ре-
бер (а, в), которому присваиваем номер 1;
- зачеркиваем ребро (а, в) и переходим к вершине в;
- продолжаем процесс, пока не будут занумерованы все ребра
графа;
- мост выбираем только тогда, когда нет других возможностей.
Полученная последовательность ребер и определяет эйлеров цикл.
Отметим, что наличие эйлерова цикла в графах электрических,
телефонных и железнодорожных линий позволяет оптимизировать
их покомпонентное тестирование.
2.3. Гамильтоновы графы
Ирландский математик Вильям Гамильтон в 1857 г. предложил
игру, названную «Кругосветное путешествие».
Пусть 20 городов расположены в вершинах правильного додека-
эдра (n = 20, m = 30, f = 12), моделирующего Землю и представлен-
ного на рис. 2.13. Необходимо пройти по рёбрам через все вершины
додекаэдра (через все города) и вернуться в исходный пункт так, что
ни в одну вершину нельзя заходить более одного раза.

Страницы