ВУЗ:
Составители:
Рубрика:
Глава 2. Плоские и планарные графы 61
Справедливы следующие утверждения [11, 15]:
1. Каждый негамильтонов двусвязный граф содержит тэта-под-
граф.
2. Если ⎪G⎪ = n ≥ 3 и для любой его вершины u ∈ G степень
ν
u
≥ n/2, то G – гамильтонов граф.
3. Если для любой пары u и w несмежных вершин графа G поряд-
ка n ≥ 3 выполняется неравенство ν
u
+ ν
w
≥ n, то G – гамильтонов
граф.
4. Всякий полный граф является гамильтоновым.
5. В гамильтоновом графе нет точек сочленения, т.е. гамильтонов
граф неразделим.
6. В каждом турнире существует гамильтонов путь.
7. Сильно связный турнир является гамильтоновым орграфом.
Отметим, что гамильтонов граф не обязательно является планар-
ным.
В 1967 г. социолог C. Милграм предложил гипотезу «тесного
(маленького) мира» («small world») – каждого человека можно свя-
зать с любым другим человеком на земном шаре цепочкой из шести
знакомых [39]. Позднее эмпирически было доказано, что подобным
свойством обладают структуры многих социальных технических
систем. Например: электроэнергетические сети, WWW-сети, ней-
ронные сети, сети научного сотрудничества и др.
Для описания растущей во времени структуры, обладающей
свойством «тесного мира», и анализа ее стойкости можно использо-
вать аппарат фрактальных графов.
2.4. Гиперкуб и его свойства
Рассмотрим два графа G
i
(V
i
, E
i
), (i = 1,2). Их произведением назы-
вается граф G(V, E), вершины которого V(G) = V
1
× V
2
− декартово
произведение множества вершин исходных графов. Множество ре-
бер E(G) при этом определяется по правилу: вершины u = (u
1
, u
2
) и
v = (v
1
, v
2
) – смежные в графе G ⇔, когда или u
1
= v
1
, а u
2
, v
2
смеж-
ные в G
2
, или u
2
= v
2
и u
1
, v
1
являются смежными в G
1
[15]. При этом
⎮V⎮ = ⎮V
1
⎮·⎮V
2
⎮, ⎮E⎮ = ⎮V
1
⎮·⎮E
2
⎮ + ⎮V
2
⎮·⎮ E
1
⎮.
Страницы
- « первая
- ‹ предыдущая
- …
- 59
- 60
- 61
- 62
- 63
- …
- следующая ›
- последняя »
