Дискретная математика. Громов Ю.Ю - 61 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

61
зить его в традиционном для двудольных графов виде (с разбиением
множества вершин на два подмножества).
11. ПЛАНАРНОСТЬ
Рассмотрим топологические свойства неориентированных графов,
которые определяются топологическими инвариантами относительно их
гомеоморфных преобразований.
Два графа называются гомеоморфными графами, если они изо-
морфны с точностью до вершин степени два. Другими словами, два графа
гомеоморфны тогда и только тогда, когда они преобразуются до изо-
морфных друг другу графов заменой некоторых рёбер простыми цепями
какой-нибудь длины.
Граф называется планарным, если его можно изобразить на плоско-
сти так, чтобы рёбра пересекались только в вершинах. Проблема харак-
теризации планарных графов долгое время оставалась нерешённой.
В 1927 г. советский математик Л.С. Понтрягин (1908 − 1988) доказал (но
не опубликовал) критерий планарности, который независимо от него в
1930 г. был открыт и опубликован польским математиком К. Куратов-
ским (1896 − 1980).
1
2
3
4
5
6
7
1
2
3
4
5
6
7
а) б)
a
b
c
d
e
f
g
h
a
b
c
e
d
f
g
h
1
2
3
4
5
6
7
в) г)
1
2
3
4
5
6
7
a
b
c
d
e
f
g
h
k
a
b
c
d
e
f
g
h
k
д) е)
1
2
3
4
5
6
7
1
2
3
4
5
6
7
a
b
c
d
e
f
g
h
k
m
a
b
c
d
e
f
g
k
h
m

Страницы