Теория графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
называется лесом. Любая цепь в графе без циклов является простой; любая часть такого графа также будет графом без циклов.
Рис. 14Рис. 15
Пример дерева показан на рис.14, здесь же показаны висячие вершины, на рисунке они выделены закрашенными кружками (вершина дерева, степень которой равна единице, называется висячей вершиной).
Пример леса показан на рис.15.
Постройте какое-нибудь дерево с пятью вершинами и подсчитайте число ребер в полученном графе. Оказывается, что в любом дереве с пятью вершинами всегда будет четыре ребра.
Теорема: дерево с n вершинами имеет n-1 ребро.
Для того, чтобы из одного дерева Г, не являющегося изолированной вершиной, получить два дерева с теми же вершинами, необходимо удалить из Г одно ребро. Для образования трех деревьев необходимо удалить из Г два каких-нибудь ребра. Самое большее из дерева Г с n вершинами можно получить n деревьев, каждое из которых является изолированной вершиной. Для этого необходимо удалить n-1 ребро из дерева Г. Итак, действительно, в дереве с n вершинами n-1 ребро.
Задача. Проводится эксперимент, при котором морскую свинку пускают в лабиринт (рис.16). Сколькими способами она может попасть к пище, если она ни в один тупик не заходит более одного раза, причем, попав в тупик, возвращается на перекресток, с которого свернула в этот тупик. Нарисуйте дерево всевозможных маршрутов морской свинки к пище.
Рис. 16
Ответ: 8 способами
Рис. 17
2. Расстояния в графах. Диаметр, радиус, центр графа
Пусть G = - связный неорграф, Vi, Vj - две его несовпадающие вершины.
Длина кратчайшего (Vi, Vj)-маршрута называется расстоянием между вершинами Vi и Vj и обозначается через ? (Vi, Vj).
Положим ? (Vi, Vj) = 0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:
1) ? (Vi, Vj) ? 0;
2) ? (Vi, Vj) = 0 - Vi = Vj
3) ? (Vi, Vj) = ? (Vi, Vj) - симметричность
4) ? (Vi, Vj) ? ? (Vi, Vj) + ? (Vj, Vк) - неравенство треугольника.
Если V = {V1, V2,…, Vn}, то матрица Р = (рi,j) = ? (Vi, Vj), называется матрицей расстояний (где матрица Р симметрична).
Для фиксированной вершины V величина Е (v) = мах { ? (Vi, Vj) | Vj є V} называется эксцентриситетом вершины V. Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее.
Если Р-матрица расстояний, то эксцентриситет Е (Vi) равен наибольшему из числе, стоящих в i-й строке.
Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d (G) : d (G) = vf[ {E(v) | v є V}. Вершина V называется периферийной, если Е (v) = d (G).
Рассмотрим пример. Найдем диаметр графа G, изображенный на рис.18. Матрица расстояний Р имеет вид:
Рис. 18
Отсюда Е (1) = 3, Е (2) = 2, Е (3) = 3, Е (4) = 2, Е (5) = 2 и, следовательно, d (G) = 3. Вершины 1 и 3 являются периферийными.
Минимальный из эксцентриситетов графа G называется его радиусом и обозначается через r (G) : r (G) = min {E (vi) | vi є V}.
Вершина V называется центральной, если Е (v) = r (G).
Множество всех центральных вершин графа называется его центром.
Рассмотрим соответствующий пример. Радиус графа, показанного на рис.18, равен 2, а его центром является множество {2, 4, 5}.
Задача нахождения центральных вершин возникает в практической деятельности людей. Пусть, например, граф представляет собой сеть дорог, т.е. вершины соответствуют населенным пунктам, а ребра - дорогам между ними. Требуется оптимально разместить больницы, пункты обслуживания и т.п. В подобных ситуациях оптимизация заключается в минимизации расстояния от места обслуживания до наиболее удаленного населенного пункта. Следовательно, местами размещения должны быть центральные вершины графа. Реальные задачи отличаются от этой идеальной темы, что приходится учитывать и другие обстоятельства - расстояния между населенными пунктами, стоимость, время проезда и т.д.
Дерево - одно из наиболее часто встречающихся в теории графов понятий (рис.19).
Ясно, что особое место в дереве занимают не только висячие вершины. Выделяются в этих деревьях и вершины, отмеченные двойным кружком. Такие вершины называют корневыми.
Корневую вершину нетрудно также выделить у деревьев на рисунках 20, 21, 22.
В первом случае корневой вершиной является единственная вершина графа А, во втором - вершина С, в третьем (такое дерево, все вершины которого, кроме одной, висячие, называют звездой) - вершина А. Но какие вершины считать корневыми в графах, которые изображены на рисунках 23, 24 и 25?
Естественно считать, что все эти три дерева имеют по две корневые вершины. У дерева на рисунке 23 - это А и В, у дерева на рисунке 24 - это С и Д, у дерева на рисунке 25 - это А и В.
Расстоянием d (Vi, Vj) между вершинами Vi и Vj графа G называют длину кратчайшего пути, их соединяющего. (Если граф G-дерево, то путь соединяющий вершины Vi и Vj, единственный).
Подсчитаем для каждой вершины дерева, изображенного на рисунке 26, наибольшее из расстояний до всех остальных его вершин и запишем эти числа на рисунке возле вершин (рис.27).
Наибольшее из таких чисел называют диаметром графа (в данном случае дерева), наименьшее - радиусом графа.
Вершины дерева, для которых максимальное из расстояний до других вершин равно радиусу, называются корневыми. Для дерева, изображенного на рисунке 26, диаметр равен 5, а радиус равен 3; корневые вершины - А и В.
Задача. Подсчитайте диаметр и радиус графа, изображенного на рисунке:
а) 18;б) 24;в) 25.
Английский математик А.Кэли в 1875 году опубликовал первую работу п