Реферат на тему: Теория Графов. Мадрахимова Виола 1-курс 100а приняла

Основные теоремы теории графов
Предложение 1. 2p= ∑ p(α) , α ∈ V.
Доказательство. Сумма ∑ p(α) , α ∈ V,учитывает каждое ребро α=b,c два раза: первый раз при вычислении p(b), второй раз при вычислении p(c).
Следствие 1. Пусть G=(V,E) – однородный граф, т.е. степени всех вершин равны между собой (и равны, например, числу k). Тогда p = k b2 . В частности, если k – нечётное число, то число вершин является чётным. Вершина α ∈ V называется нечетной, если p(α) – нечётное число.
Следствие 2. Число нечётных вершин графа является чётным.
Доказательство следует из равенства ∑ p(α) =2 p, α ∈ V и того, что сумма нечетного числа нечетных слагаемых является нечетным числом.
Упражнение 1. Число студентов в АГУ, имеющих нечетное число знакомых в АГУ, является четным.
Упражнение 2. (городская олимпиада, Барнаул, 1997 г., 8 класс). Можно ли соединить между собой проводами 7 телефонов так, чтобы каждый был соединен ровно с тремя другими?
Теорема (Л. Эйлер, 1752 г.). Пусть G = (V,E) – плоский связный граф. Тогда p + 2 = Г + b (в число граней включена одна неограниченная грань).
Например, рассмотрим граф куба:

Для него b = 8, p = 12, Г = 6 и p + 2 = 14 = b + Г.
Доказательство теоремы проведем индукцией по числу ребер p. Если p = 0, то b = 1 и Г = 1. Если p = 1, то граф имеет один из следующих видов (рис. 3):

В первом случае -- p = 1, b = 2 и Г = 1; во втором - p = 1, b = 1 и Г = 2. Ясно, что в каждом из этих случаев справедливо равенство p + 2 = b + Г. Если G содержит вершину α ∈ V степени 1, то удаляя α и инцидентное с ним ребро, мы получим опять связанный планарный граф G' = (V', E'), в котором
p' = p – 1, b'= b – 1, Г' = Г. По предположению индукции p' + 2 = (p – 1) + 2 = b' + Г' = (b-1) + Г или p + 2 = b + Г. Итак, можно считать, что для любой вершины α ∈ V p (α) ≥ 2. Докажем, что G содержит цикл. Пусть v1∈V и v2 - смежная вершина с v1. Если v1= v2, то получаем петлю.
Если v1≠ v2, то из неравенства p (v2) ≥2 следует, что существует вершина v3∈V, смежная с v2. Рассуждая аналогично, мы получим последовательность инцидентных вершин v1, v2, v3, … Так как V <∞, то в этой последовательности встретится вершина vk, которая встречалась раньше. Выбирая k минимальным с этим свойством, мы получим цикл. Удалим в этом цикле одно ребро. Мы получим новый связный планарный граф G' = (V', E'), в котором p' = p – 1, b'= b, Г' = Г – 1. По предположению индукции p' + 2 = (p – 1) + 2 = b' + Г' = b + (Г – 1) или p + 2 = b + Г. Теорема доказана.
Задача 1. Доказать, что для «хорошего» графа p = 3b – 6.
Указание. В «хорошем» графе все грани являются треугольными. Поэтому 3Г = 2p и Г = 23 p. Подставим это выражение в формулу Эйлера p + 2 = b + 23 p. Получим, что p3 = b – 2.
Задача 2. Внутри треугольника взято m точек, которые соединены друг с другом и вершинами исходного треугольника так, что исходный треугольник разбился на меньшие треугольники с непересекающимися сторонами. Доказать, что число маленьких треугольников равно (2m + 1), т.е. не зависит от способа соединения.
Указание. Согласно предыдущей задаче p = 3b – 6 = 3(m + 3) – 6 = 3m + 3 и Г = (p + 2) – b = 3m + 5 – (m+3) = 2m +2. В нашем графе одна грань – внешняя. Поэтому искомое число треугольников равно (2m + 1).