Дискретная математика. Кулаков Ю.В - 44 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

3 Получить цикломатические матрицы C(G) для всех графов из задачи 1.
4 Установить, является ли двудольным граф:
Двудольные графы представить графически с отдельным расположением двух множеств вершин.
9 ПЛАНАРНОСТЬ
Рассмотрим топологические свойства графов. Эти свойства определяются
топологическими инвариантами относительно гомеоморфных преобразований.
Два графа являются гомеоморфными, если они изоморфны с точностью до
вершин степени два. Другими словами, два графа гомеоморфны, если они преобразуются до графов,
изоморфных друг другу, заменой некоторых ребер цепями какой-нибудь длины.
Граф называется планарным, если его можно изобразить на плоскости так,
чтобы ребра пересекались только в вершинах. Проблема характеризации планарных графов долгое вре-
мя оставалась нерешенной. В 1927 г. Понтрягин Л. С. доказал (но не опубликовал) критерий планарно-
сти, который независимо от него был открыт и опубликован польским математиком Куратовским в 1930
г.
Теорема (теорема Л. С. Понтрягина). Граф планарен тогда и только то-
гда, когда он не содержит подграфа или частичного графа, гомеоморфного F
5
или K
3, 3
(рис. 22, а, б).
a
b
c
g
h
а)
б)
в)
г)
a
d
e
f
g
b
d
e
f
g
a
b
d
e
h
a
b
c
g
h
а)
б)
в)
г)
a
b
d
e
f
a
d
e
f
b
g
h
a
d
e
f
c
b
c
g
h
a
d
e
f
k
l
c
g
h
1
2
3
4
5
6
7
1
2
3
4
5
6
7
1
2
3
4
5
6
7
1
2
3
4
5
6
7
; ;
; .
а)
б)
Рис.
a
c
d
e
g
f
b
a(b)
c
d
e
f
g
Ри
с

Страницы