Деревья и графы реферат

Обновлено: 05.07.2024

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Дурак видит не то самое дерево,

что видит умный .

(Вильям Блейк) 1

Тема: Графы и деревья.

Цель : исследовать понятие графы и деревья, их применимость в точных науках.

Изучить мнение участников образовательного процесса об исследуемых понятиях

Изучить разновидности графов, их составные элементы.

Исследовать возможности применения графов и деревьев в предметных областях.

Использовать данные понятия при решении прикладных задач.

Актуальность – исследование понятий в новых областях науки.

Предмет исследования – зависимости и связи между величинами, предметами.

Объект исследования – графы и деревья.

Методы исследования : анкетирования, исследование первоисточников (энциклопедий, словарей и др. научной литературы), анализ, сопоставление.

Глава 1: Немного о графах и деревьях

Что такое граф

Граф – это множество точек (для удобства изображения на плоскости) и попарно соединяющих их линий (не обязательно прямых). В графе важен только факт наличия связи между двумя вершинами. В графах не бывает петель – рёбер, соединяющих некоторую вершину саму с собой. Кроме того, в классическом графе не бывает двух различных рёбер, соединяющих одну и ту же пару вершин. Ребро и вершина называются инцидентными друг другу, если вершина является одним из концов ребра. Любому ребру инцидентно ровно две вершины, а вот вершине может быть инцидентно произвольное количество рёбер, это количество определяет степень вершины. Изолированная вершина вообще не имеет инцидентных ей рёбер (её степень равна 0).

Таким образом, степенью (валентностью) вершины называется количество рёбер, выходящих из данной вершины. Например, на рисунке 1 вершина А имеет степень 3, вершина В-степень 2, вершина С- степень1, вершина D - степень 0. Если мы сложим степени всех вершин некоторого графа, то при этом подсчёте каждое ребро будет учтено дважды (оно ведь соединяет две вершины!). Поэтому сумма степеней всех вершин графа в два раза больше, чем число его рёбер. В частности, сумма степеней всех вершин графа чётная.

2 Денеш Кёниг (1884 – 1944) – венгерский математик, написавший первую книгу по теории графов.

3 Леонард Эйлер (1707 – 1783) – крупнейший математик Х VIII века. В 1727 г. По приглашению Петербургской академии наук был в России, и единодушно был признан первым математиком мира.

Две вершины называются смежными , если они являются разными концами одного ребра (иными словами, эти вершины инцидентны одному ребру). Аналогично, два ребра называются смежными , если они инцидентны одной вершине.

Путь в графе – это последовательность вершин (без повторений), в которой любые две соседние вершины смежные. Например, в графе, изображённом на рисунке (рис.2), есть два различных пути из вершины а в вершину с: а dbc и а bc .

Вершина v достижима из вершины u , если существует путь, начинающийся в u и заканчивающийся в v . Граф называется связным , если все его вершины взаимно достижимы.

Длина пути – количество рёбер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc (рис. 2) – 3 и 2 соответственно.

Расстояние между вершинами u и v – это длина кратчайшего пути от u до v . Из этого определения видно, что расстояние между вершинами а и с на рис.2 равно 2.

Цикл – это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь а bda в графе на рис.2.

Ориентированный граф (орграф) – это граф, все рёбра которого имеют направление. Такие направленные рёбра называются дугами . На рисунках дуги изображаются стрелочками (см. рис.3).

В отличие от рёбер, дуги соединяют две неравноправные вершины: одна из них называется началом дуги (дуга из неё исходит ), вторая – концом дуги (дуга в неё входит ). Можно сказать, что любое ребро – это пара дуг, направленных навстречу друг другу.

Взвешенный (другое название: размеченный) граф (или орграф) – это граф (орграф), некоторым элементам которого (вершинам, рёбрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными рёбрами. Числа – пометки носят различные названия: вес , длина, стоимость .

Замечание : обычный (не взвешенный) граф можно интерпретировать как взвешенный, все рёбра которого имеют одинаковый вес 1.

Длина пути во взвешенном (связном) графе – это сумма длин (весов) тех рёбер, из которых состоит путь. Расстояние между вершинами – это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины а до вершины d во взвешенном графе, изображённом на рисунке (рис. 4), равно 6.

1.2. Способы представления графов.

Один и тот же граф можно нарисовать разными способами. Например, если в турнире пяти команд A , B , C , D , E , команда А сыграла с В, D и E , команда С сыграла с В и D , а D сыграла с Е, то рисунки (рис. 5-6) правильно изображают описанную ситуацию.

Рис. 5 Рис. 6

Одинаковые, но по-разному нарисованные графы называют изоморфными. Например, графы на следующих рисунках (рис. 7-9) изоморфны.

Рис.7 Рис. 8 Рис. 9

Другим способом представления графов является матрица смежности.

Матрица смежности S _m – это квадратная матрица размером NxN ( N – количество вершин в графе), заполненная единицами и нулями по следующему правилу: Если в графе имеется ребро е, соединяющее вершины u и v , то S _m ( u , v ) = 1. В противном случае матрица смежности равна нулю.

Матрица смежности для графа, изображённого на рис. 2, выглядит следующим образом:

Матрица смежности симметрична относительно главной диагонали, то есть, если существует ребро из вершины а в вершину b , то существует и ребро из b в а. Задать взвешенный граф при помощи матрицы смежности тоже возможно. Необходимо лишь внести небольшое изменение в определении:

Если в графе имеется ребро е, соединяющее вершины u и v , то S _m ( u , v ) = 1,

в противном случае S _m ( u , v ) = 0. В этом случае вместо матрицы смежности используют весовую матриц , в клетках которой записывают веса рёбер, а если ребра нет, то клетку оставляют пустой. Если у нас имеется матрица смежности или весовая матрица, то по ней легко построить граф. Например, для следующей весовой матрицы построить взвешенный граф (рис.10):

А 3 B 7 5 3 F

4 D 2 E

1.3 Деревья как частный случай графов

Существует довольно много равносильных определений деревьев.

Дерево – это связный граф без циклов.

Дерево – это связный граф, в котором при N вершинах всегда ровно N – 1 ребро.

Дерево – это граф, между любыми двумя вершинами которого существует ровно один путь.

Аналогичным образом определяется и ориентированное дерево (рис.11).– как орграф, в котором между любыми двумя вершинами существует не более одного пути

Дерево как связный граф, не содержащий циклов. Перечень основных свойств деревьев. Общее понятие про орграф. Содержание теоремы А. Кэлли. Сущность понятия "подграф". Пример алгоритма построения каркаса в связном графе, особенности его обоснования.

Рубрика	Математика
Вид	реферат
Язык	русский
Дата добавления	18.04.2012
Размер файла	145,9 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Министерство образования Республики Беларусь

Рассмотрим частный вид графов, широко используемых, например, в теории электрических цепей, химии, вычислительной технике и в информатике.

Определение 1. Деревом называется связный граф, не содержащий циклов. Любой (в том числе несвязный) граф без циклов называется ациклическим. Несвязный граф, каждая компонента связности которого является деревом, называется лесом. Можно сказать, что деревья являются компонентами леса. На рис.1 изображены два дерева G1, G2 и лес G3.

Сформулируем основные свойства деревьев. Сделаем это в виде совокупности утверждений, которые эквивалентны между собой (т.е. из любого утверждения следует любое другое.

Теорема 1. Пусть G(X, E) - неориентированный граф с p вершинами и q ребрами. Тогда следующие утверждения эквивалентны.

1. G есть дерево.

2. Любые две различные вершины x и y графа G соединены единственной простой цепью.

3. G - связный граф, утрачивающий это свойство при удалении любого из его ребер.

4. G - связный граф и p = q + 1.

5. G - ациклический граф и p = q + 1.

6. G - ациклический граф, причем если любые две его вершины x и y соединить ребром e, то в полученном графе будет ровно один простой цикл.

Для доказательства теоремы достаточно доказать следующую цепочку следствий: 1 2 3 4 5 6 1, так как это означает, что из любого утверждения 1 - 6 выводится любое другое.

1 2. Так как граф связен, то любые две его вершины можно соединить простой цепью. Пусть 1 и 2 - две различные простые цепи, соединяющие вершины x и y. Если цепи 1 и 2 не имеют общих вершин, за исключением вершин x и y, то есть простой цикл. Предположим, что цепи 1 и 2 имеют общие вершины, отличные от x и y. Пусть z - первая из таких вершин при движении от вершины x к вершине y и пусть 1(x, z) и 2(x, z) - части цепей 1 и 2, взятые от вершины x до вершины z. Тогда - простой цикл. Это противоречит тому, что граф ацикличен, и поэтому 1=2, т.е. утверждение 2 доказано.

2 3. Граф G - связен, поскольку любые две его различные вершины x и y соединены простой цепью. Возьмем некоторое ребро графа e = (x, y). Согласно 2 простая цепь = между вершинами x и y единственна. Если ребро e удалить, то вершины x и y будет невозможно соединить простой цепью, и полученный граф будет несвязным. Утверждение 3 доказано.

3 4. По условию 3 граф связен. Соотношение p = q + 1 докажем по индукции. Если граф имеет две вершины и удовлетворяет 3, то он выглядит так:

В этом случае p = 2, q = 1 и соотношение p = q + 1 выполняется. Предположим теперь, что соотношение верно для всех графов, удовлетворяющих 3 и имеющих меньше, чем p вершин, и докажем его для графа G с p вершинами. Удалим из графа G произвольное ребро e. Тогда новый граф Gґ будет несвязным и будет состоять из двух связных компонент G1 и G2. По предположению индукции имеем

p1 = q1 + 1, p2 = q2 + 1,

где pi - число вершин компоненты Gi, qi - число ее ребер. Следовательно,

p = p1 + p2, q = q1 + q2 + 1,

поэтому p = q1 + q2 + 2 = q + 1, и свойство 4 доказано.

4 5. Предположим, что граф G, удовлетворяющий 4, имеет простой цикл длиной l 1. Этот цикл содержит l вершин и l ребер. Для любой из p - l вершин, не принадлежащих циклу , существует инцидентное ей ребро, ле-жащее на кратчайшей цепи (т.е. цепи минимальной длины), идущей от данной вершины к некоторой вершине цикла . Все такие ребра попарно различны. Если вершины x1 и x2 инцидентны одному такому ребру e, то e = (x1, x2), и кратчайшая цепь 1 для вершины x1 проходит через вершину x2, а кратчайшая цепь 2 для вершины x2 проходит через вершину x1 (рис. 2). Это противоречит тому, что цепи 1 и 2 - кратчайшие. Общее число ребер q в графе G в этом случае не меньше, чем l + p - l = p, т.е. q p, что противоречит соотношению p = q + 1. Отсюда следует, что G - ациклический граф, и утверждение 5 доказано.

5 6. Так как G - ациклический граф, то каждая его компонента связности Gi (i = 1, 2, …, k) является деревом. Для каждой компоненты Gi имеем в соответствии с 5 pi = qi + 1, откуда , т.е. p = q + k. С другой стороны, p = q + 1, поэтому k = 1, т.е. граф G связен. Таким образом, G - дерево. Тогда (см. 2 ) любые две различные вершины x и y графа G соединены единственной простой цепью. Если добавить ребро между несмежными вершинами x и y, то оно образует с указанной цепью единственный простой цикл. Утверждение 6 доказано.

6 1. По условию 6 G - ациклический граф. Если граф G не является связным, то возьмем вершины x и y из различных компонент связности графа G и соединим их ребром e. Построенный граф является, как и граф G, ациклическим. Это противоречит свойству G, поэтому G - связный граф, и свойство 1 доказано. Таким образом, доказана и теорема 1.

Определение, аналогичное дереву, можно ввести и для орграфа.

Определение 2. Орграф G(X, E) называется прадеревом или ориентированным деревом, растущим из корня x0, при следующих условиях:

1. Неориентированный граф G', соответствующий графу G, является деревом.

2. Единственная простая цепь между x0 и любой другой вершиной x графа G' является путем в орграфе G, идущим из вершины x0 в вершину x.

На рис. 4 изображено ориентированное дерево.

В неориентированном графе G(X, E) вершина x называется концевой или висячей, если (x) = 1, т.е. если этой вершине инцидентно единственное ребро e. Это ребро также называется концевым или висячим. С висячими вершинами связана следующая теорема.

Теорема 2. В любом дереве G(X, E) с p 2 вершинами имеется не менее двух концевых вершин.

Доказательство. Пусть q - число ребер дерева G. В силу теоремы 1 p = q + 1. Кроме того, из теоремы 1.1 имеем

Таким образом, получаем

Предположим, что x0 - единственная концевая вершина в дереве G. Тогда (x0) = 1, (x) 2, если x x0. Отсюда

Неравенство (2) противоречит (1), поэтому либо концевых вершин нет, либо их по крайней мере две. Если концевых вершин в G нет, то (x) 2 для всех xX. Тогда

Неравенство (3) тоже противоречит (1). Отсюда следует, что концевых вершин в G две или больше. Теорема доказана.

Важным является вопрос о том, сколько существует деревьев с заданным числом вершин. Для деревьев с помеченными вершинами (например, пронумерованными) или для помеченных деревьев ответ на этот вопрос дает следующая теорема.

Теорема 3. (А. Кэли, 1897 г.). Число помеченных деревьев с p вершинами равно pp-2.

Доказательство. Пусть G(X, E) - дерево с p помеченными вершинами. Для простоты предположим, что вершины пронумерованы в произвольном порядке числами 1, 2, …, p. Рассмотрим способ, позволяющий однозначно закодировать дерево G.

В соответствии с теоремой 2 дерево G имеет концевые вершины. Пусть x1 - первая концевая вершина в последовательности 1, 2, …, p и пусть e1 = (x1, y1) - соответствующее концевое ребро. Удалим из дерева вершину x1 и ребро e1. Получим новое дерево G1 с числом вершин p - 1. Найдем теперь пер--вую концевую вершину x2 дерева G1 в последовательности вершин 1, 2, … …, p из множества \, далее возьмем концевое ребро e2 = (x2, y2) и удалим из G1 x2 и e2. Эту процедуру последовательно повторяем. Через (p - 2) шага остается дерево из двух вершин xp-1, yp-1 и одного ребра ep-1 = (xp-1, yp-1). Рассмотрим последовательность вершин

Очевидно, что по данному дереву последовательность строится однозначно. Покажем теперь, что по данной последовательности вершин (G) дерево G можно восстановить однозначно. В последовательности 1, 2, …, p существуют вершины, не принадлежащие (G). Выберем первую из них x1 и построим ребро e1 = (x1, y1). Затем удалим x1 из последовательности 1, 2, …, n и y1 удалим из (G). Аналогичным образом построим ребро e2 = (x2, y2). Продолжая этот процесс, мы однозначно восстановим дерево G. Рассмотрим пример.

(G) и список вершин

Рассмотренный пример позволяет отметить следующие две особенности:

1. В списке (G) вершины могут повторяться.

2. При восстановлении дерева последнее ребро соединяет вершину yp-2 и оставшуюся в списке 1, 2, …, p вершину не равную yp-2.

Итак, существует взаимно однозначное соответствие между множеством помеченных деревьев с p вершинами и множеством последовательностей вершин (G). Число таких последовательностей равно, очевидно, pp-2, что и требовалось доказать.

Отметим, что среди pp-2 помеченных деревьев с p вершинами могут быть и изоморфные.

Определение 3. Подграф G1(X1, E1) неориентированного графа G(X, E) называется каркасом, или основным деревом графа G, если G1 - дерево и X = X1.

Теорема 4. Граф G(X, E) тогда и только тогда обладает каркасом, когда он связен.

Доказательство. Необходимость этого очевидна. Докажем достаточность. Пусть G(X, E) - связный граф. Выясним, есть ли в графе G такое ребро, удаление которого не нарушает связности графа G. Если таких ребер нет, то граф есть дерево в соответствии с теоремой 1. Если же такое ребро, например e, существует, то выбросим его и придем к графу G1(X, E\). Затем указанную процедуру проделываем с графом G1 и т.д. Через конечное число шагов будет построен, очевидно, каркас графа G. Теорема доказана.

Доказательство теоремы дает алгоритм построения некоторого каркаса в связном графе. Однако связный граф может иметь несколько каркасов, поэтому естественно поставить задачу выбора каркаса, удовлетворяющего дополнительным условиям.

Определение 4. Графом с нагруженными ребрами (нагруженным графом) называется неориентированный граф G(X, E), каждому ребру eE которого поставлено в соответствие число (e) 0, называемое весом или длиной ребра e.

Аналогично можно определить нагруженный орграф.

Поставим задачу нахождения такого каркаса G1(X, E1) в нагруженном графе G(X, E), для которого сумма

минимальна. Каркас с таким свойством называется минимальным каркасом. В соответствии с теоремой 4 каждый нагруженный связный граф обладает минимальным каркасом. Эта задача возникает при проектировании линий связи и электропередач, дорог, трубопроводов и т.п., когда требуется соединить системой каналов связи заданные узлы так, чтобы любые два узла были связаны (возможно, через другие узлы), а общая длина каналов связи была минимальной; при этом узлы можно считать вершинами нагруженного графа, весам ребер которого соответствует длина возможного канала связи между соответствующими узлами. Тогда искомая сеть каналов будет минимальным каркасом этого графа.

Алгоритм построения минимального каркаса

Пусть G(X, E) - связный нагруженный граф с p вершинами.

Шаг 1. В качестве первого ребра искомого минимального каркаса выбираем ребро e1 с наименьшим весом (e1). Если таких ребер несколько, то берем любое из них.

Шаг 2. В качестве второго ребра берем ребро e2 из множества E\, имеющее наименьший вес (e2), и такое, что множество не содержит простых циклов. Если таких ребер несколько, то берем любое из них.

Шаг 3. В качестве третьего ребра выбираем такое ребро e3 из множества E\, которое имеет наименьший вес (e2) и для которого множество не содержит простых циклов. Если таких ребер несколько, берем любое из них.

Указанный процесс повторяется и через некоторое число k шагов дает множество E = , к которому нельзя добавить ребро без появления цикла. Подграф G1(X, E1) и является минимальным каркасом графа G(X, E).

В силу свойства 6 из теоремы 1 построенный подграф G1(X, E1) является деревом, поэтому k = p -1. Доказательство минимальности каркаса G1(X, E1) разобьем на два этапа. Пусть сначала G(X, E) - полный граф, у которого веса всех ребер различны, и пусть G2(X, E2) - минимальный каркас графа G. Если E2 E1, то рассмотрим el - первое из ребер множества E1, не принадлежащее E2. В графе в силу свойства 6 теоремы 1 существует единственный простой цикл . Цикл содержит ребро e0E1. Граф G3(X, E3), где , не содержит циклов и имеет n - 1 ребро, поэтому он является деревом. Множество содержится в E2 и поэтому не содержит циклов. Тогда в силу рассмотренного выше алгоритма (e0) > (el). Отсюда следует, что суммарный вес дерева G3(X, E3) меньше веса дерева G2(X, E2). Это противоречит минимальности каркаса G2, поэтому E2 = E1 и G1(X, E1) - единственный минимальный каркас графа G.

Пусть теперь G(X, E) - произвольный нагруженный связный граф. Если (e1) = (e2), то сделаем замену

дерево граф подграф каркас

взяв такое , чтобы сохранились соотношения весов (e1) и (e2) с другими весами. Сделаем граф G полным, добавив такие ребра di, что . В полученном графе единственным минимальным каркасом будет каркас, полученный с помощью рассмотренного алгоритма. Легко видеть, что этот каркас будет минимальным и в исходном графе G(X, E).

На рис. 5 изображены нагруженный граф G и его минимальный каркас G1.

ЛИТЕРАТУРА

1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко. - М.: изд-во МГТУ им. Н.Э. Баумана, 2001.- 744 с. (Сер. Математика в техническом университете; Вып XIX).

Подобные документы

Вид графов, используемых в теории электрических цепей, химии, вычислительной технике и в информатике. Основные свойства деревьев. Неориентированный граф. Алгоритм построения минимального каркаса. Обоснование алгоритма. Граф с нагруженными ребрами.

реферат [131,8 K], добавлен 11.11.2008

Понятия теории графов, их связность и задача о кратчайшей цепи. Программная реализация метода Дейкстры, его сравнение с методом простого перебора. Описание логики программного модуля. Примеры работы программы нахождения кратчайшей цепи в связном графе.

курсовая работа [330,2 K], добавлен 25.11.2011

Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.

курсовая работа [228,5 K], добавлен 30.01.2012

Рассмотрение понятия и видов графов как совокупности непустого конечного множества элементов; условия их связанности. Доказательства существования замкнутых Эйлеровой, Гамильнотовой и бесконечной цепей. Ознакомление с элементарными свойствами деревьев.

курсовая работа [1,4 M], добавлен 10.02.2012

Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.

презентация [150,3 K], добавлен 16.01.2015

Основополагающие понятия теории графов. Определение эквивалентности, порождаемое группой подстановок, и доказательство леммы Бернсайда о числе ее классов. Понятие перечня конфигурации и доказательство теоремы Пойа. Решение задачи о перечислении графов.

курсовая работа [649,2 K], добавлен 18.01.2014

Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".

Сформулируем основные свойства деревьев. Сделаем это в виде совокупности утверждений, которые эквивалентны между собой (т.е. из любого утверждения следует любое другое) .

Теорема 1. Пусть G(X, E) – неориентированный граф с p вершинами и q ребрами. Тогда следующие утверждения эквивалентны.

6 . G – ациклический граф, причем если любые две его вершины x и y соединить ребром e, то в полученном графе будет ровно один простой цикл.

Для доказательства теоремы достаточно доказать следующую цепочку следствий: 1  2  3  4  5  6  1 , так как это означает, что из любого утверждения 1 – 6 выводится любое другое.

1 2 . Так как граф связен, то любые две его вершины можно соединить простой цепью. Пусть 1 и 2 - две различные простые цепи, соединяющие вершины x и y. Если цепи 1 и 2 не имеют общих вершин, за исключением вершин x и y, то есть простой цикл. Предположим, что цепи 1 и 2 имеют общие вершины, отличные от x и y. Пусть z – первая из таких вершин при движении от вершины x к вершине y и пусть 1(x, z) и 2(x, z) – части цепей 1 и 2, взятые от вершины x до вершины z. Тогда - простой цикл. Это противоречит тому, что граф ацикличен, и поэтому 1=2, т.е. утверждение 2 доказано.

2 3 . Граф G – связен, поскольку любые две его различные вершины x и y соединены простой цепью. Возьмем некоторое ребро графа e = (x, y). Согласно 2 простая цепь = между вершинами x и y единственна. Если ребро e удалить, то вершины x и y будет невозможно соединить простой цепью, и полученный граф будет несвязным. Утверждение 3 доказано.

3 4 . По условию 3 граф связен. Соотношение p = q + 1 докажем по индукции. Если граф имеет две вершины и удовлетворяет 3 , то он выглядит так:

В этом случае p = 2, q = 1 и соотношение p = q + 1 выполняется. Предположим теперь, что соотношение верно для всех графов, удовлетворяющих 3 и имеющих меньше, чем p вершин, и докажем его для графа G с p вершинами. Удалим из графа G произвольное ребро e. Тогда новый граф G´ будет несвязным и будет состоять из двух связных компонент G1 и G2. По предположению индукции имеем

4 5 . Предположим, что граф G, удовлетворяющий 4 , имеет простой цикл  длиной l  1. Этот цикл содержит l вершин и l ребер. Для любой из p - l вершин, не принадлежащих циклу , существует инцидентное ей ребро, ле¬жащее на кратчайшей цепи ( т.е. цепи минимальной длины), идущей от данной вершины к некоторой вершине цикла . Все такие ребра попарно различны. Если вершины x1 и x2 инцидентны одному такому ребру e, то e = (x1, x2), и кратчайшая цепь 1 для вершины x1 проходит через вершину x2, а кратчайшая цепь 2 для вершины x2 проходит через вершину x1 (рис. 2). Это противоречит тому, что цепи 1 и 2 – кратчайшие. Общее число ребер q в графе G в этом случае не меньше, чем l + p – l = p, т.е. q  p, что противоречит соотношению p = q + 1. Отсюда следует, что G – ациклический граф, и утверждение 5 доказано.

5 6 . Так как G – ациклический граф, то каждая его компонента связности Gi (i = 1, 2, …, k) является деревом. Для каждой компоненты Gi имеем в соответствии с 5 pi = qi + 1, откуда , т.е. p = q + k. С другой стороны, p = q + 1, поэтому k = 1, т.е. граф G связен. Таким образом, G – дерево. Тогда (см. 2 ) любые две различные вершины x и y графа G соединены единственной простой цепью. Если добавить ребро между несмежными вершинами x и y, то оно образует с указанной цепью единственный простой цикл. Утверждение 6 доказано.

6 1 . По условию 6 G – ациклический граф. Если граф G не является связным, то возьмем вершины x и y из различных компонент связности графа G и соединим их ребром e. Построенный граф является, как и граф G, ациклическим. Это противоречит свойству G, поэтому G – связный граф, и свойство 1 доказано. Таким образом, доказана и теорема 1.

2 . Единственная простая цепь между x0 и любой другой вершиной x графа G' является путем в орграфе G, идущим из вершины x0 в вершину x.

В неориентированном графе G(X, E) вершина x называется концевой или висячей, если (x) = 1, т.е. если этой вершине инцидентно единственное ребро e. Это ребро также называется концевым или висячим. С висячими вершинами связана следующая теорема.

Доказательство. Пусть q – число ребер дерева G. В силу теоремы 1 p = q + 1. Кроме того, из теоремы 1.1 имеем

Предположим, что x0 – единственная концевая вершина в дереве G. Тогда (x0) = 1, (x)  2, если x  x0. Отсюда

Неравенство (2) противоречит (1), поэтому либо концевых вершин нет, либо их по крайней мере две. Если концевых вершин в G нет, то (x)  2 для всех xX. Тогда

Неравенство (3) тоже противоречит (1). Отсюда следует, что концевых вершин в G две или больше. Теорема доказана.

Важным является вопрос о том, сколько существует деревьев с заданным числом вершин. Для деревьев с помеченными вершинами (например пронумерованными) или для помеченных деревьев ответ на этот вопрос дает следующая теорема.

Доказательство. Пусть G(X, E) – дерево с p помеченными вершинами. Для простоты предположим, что вершины пронумерованы в произвольном порядке числами 1, 2, …, p. Рассмотрим способ, позволяющий однозначно закодировать дерево G.

В соответствии с теоремой 2 дерево G имеет концевые вершины. Пусть x1 – первая концевая вершина в последовательности 1, 2, …, p и пусть e1 = (x1, y1) – соответствующее концевое ребро. Удалим из дерева вершину x1 и ребро e1. Получим новое дерево G1 с числом вершин p - 1. Найдем теперь пер¬¬вую концевую вершину x2 дерева G1 в последовательности вершин 1, 2, … …, p из множества <1, 2, …, p >, далее возьмем концевое ребро e2 = (x2, y2) и удалим из G1 x2 и e2. Эту процедуру последовательно повторяем. Через (p - 2) шага остается дерево из двух вершин xp-1, yp-1 и одного ребра ep-1 = (xp-1, yp-1). Рассмотрим последовательность вершин

Очевидно, что по данному дереву последовательность строится однозначно. Покажем теперь, что по данной последовательности вершин  (G) дерево G можно восстановить однозначно. В последовательности 1, 2, …, p существуют вершины, не принадлежащие  (G). Выберем первую из них x1 и построим ребро e1 = (x1, y1). Затем удалим x1 из последовательности 1, 2, …, n и y1 удалим из (G). Аналогичным образом построим ребро e2 = (x2, y2). Продолжая этот процесс, мы однозначно восстановим дерево G. Рассмотрим пример.

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

Задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони.

Леонард Эйлер — швейцарский, немецкий и российский математик , внёсший значительный вклад в развитие математики , а также механики , физики , астрономии и ряда прикладных наук.

В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).

На упрощённой схеме части города ( графе ) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

Граф G – упорядоченная пара (V,E), где V – множество и E семейство неупорядоченных пар элементов из V. Элементы множества V называются вершинами графа G, а элементы Е – его рёбрами. Вершины а, b ∈ V ребра α= a,b ∈ E называются его концами. Говорят, что α инцидентно своим концам, а концы, в свою очередь, инцидентны ребру α.

Мы будем рассматривать графы, у которых число вершин и число рёбер конечно. Пусть G=(V,E) – граф и α ∈ V. Число рёбер, инцидентных вершине α, называется степенью вершины α и обозначается p(α). Пусть p – число всех рёбер, b – число всех вершин и Г – число всех граней графа G=(V,E) .

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу?

Решение: Занумеруем последовательно клетки доски:

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:

Задача 3 . В Тридевятом царстве только один вид транспорта –
ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов – по 20. Докажите, что из столицы можно долететь в город Дальний.

Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.

Основные теоремы теории графов

Предложение 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

Задача 2. Внутри треугольника взято m точек, которые соединены друг с другом и вершинами исходного треугольника так, что исходный треугольник разбился на меньшие треугольники с непересекающимися сторонами. Доказать, что число маленьких треугольников равно (2m + 1), т.е. не зависит от способа соединения.

Указание. Согласно предыдущей задаче p = 3b – 6 = 3(m + 3) – 6 = 3m + 3 и Г = (p + 2) – b = 3m + 5 – (m+3) = 2m +2. В нашем графе одна грань – внешняя. Поэтому искомое число треугольников равно (2m + 1).

Задачи на применение теории графов

В данном параграфе будут рассмотрены некоторые задачи, при решении которых используется теория графов. Они считаются классическими.

Задача 1. Необходимо составить фрагмент расписания для одного дня с

учетом следующих обстоятельств:

1. учитель истории может дать либо первый, либо второй,
либо третий уроки, но только один урок;

2. учитель литературы может дать один, либо второй, либо третий урок;

3. математик готов дать либо только первый, либо только второй урок;

4. преподаватель физкультуры согласен дать только последний урок.

Сколько и каких вариантов расписания, удовлетворяющего всем вышеперечисленным условиям одновременно, может составить завуч школы?

Задача 2. В составе экспедиции должно быть 6 специалистов: биолог,

врач, синоптик, гидролог, механик и радист. Имеется 8 кандидатов, из которых и нужно выбрать участников экспедиции; условные имена претендентов: A , B , C , D , E , F , G и H.

Обязанности биолога могут исполнять E и G ,

врача – A и D , синоптика – F и G , гидролога – B и F ,

радиста – С и D , механика – C и H .

Предусмотрено, что в экспедиции каждый из них будет выполнять только одну обязанность. Кого и в какой должности следует включить в состав экспедиции, если F не может ехать без B , D – без H и C,

C не может ехать вместе с G , A – вместе с B?

Решение Вершины графа могут соединяться не только линиями, но и стрелками. Такие члены экспедиции, которые не могут ехать без других, причем в определенном графе ребра называются ориентированными . В данном графе черными стрелками указаны члены, которые не могут ехать друг без друга, а розовыми стрелками(A-B, C-G) – члены экспедиции, которые не могут ехать совместно

В результате решения задачи получили следующий состав экспедиции:

Радист – С, врач – D, гидролог – В, синоптик – F, биолог – Е, механик – Н.

Задача 3. Планета имеет форму выпуклого многогранника, причем в его вершинах расположены города, а каждое ребро является дорогой. Две дороги закрыты на ремонт. Докажите, что из любого города можно проехать в любой другой по оставшимся дорогам.

Решение. Пусть A и B – данные города. Докажем сначала,

что из A в B можно было проехать до закрытия на ремонт двух

дорог. Рассмотрим для этого проекцию многогранника на некоторую прямую, не перпендикулярную ни одному из его ребер (при такой проекции вершины многогранника не сливаются).

Пусть A' и B' – проекции точек A и B, а M' и N' – крайние точки проекции многогранника (в точки M' и N' проецируются вершины M и N ) . Если идти из вершины A так, что в проекции движение будет происходить по направлению от M' к N' , то, в конце концов, мы обязательно попадем в вершину N . Аналогично из вершины B можно пройти в N . Таким образом, можно проехать из A в B (через N ).

Если полученный путь из A и B проходит через закрытую дорогу, то есть еще два объезда по граням, для которых это ребро является общим. Вторая закрытая дорога не может находиться сразу на двух этих объездах. Значит, из города A в город B можно проехать, по крайней мере и, т. е. вершинами с нечетной степенью.

Приложение теории графов
в различных областях науки и техники

Графы и информация

Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.

Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.

Графы и биология

Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов – размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево.

Нас будет интересовать лишь один вопрос: в скольких случаях n -е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.

Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.

Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи. В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.

Созданная Эйлером теория графов нашла очень широкое применение: например, её используют при изучении транспортных и коммуникационных систем, в частности, для маршрутизации данных в Интернете .

Маршрутизация ( англ. Routing ) — процесс определения маршрута следования информации в сетях связи.

Маршруты могут задаваться административно ( статические маршруты ), либо вычисляться с помощью алгоритмов маршрутизации , базируясь на информации о топологии и состоянии сети, полученной с помощью протоколов маршрутизации (динамические маршруты).

Статическими маршрутами могут быть:

маршруты, не изменяющиеся во времени;
маршруты, изменяющиеся по расписанию;
маршруты, изменяющиеся по ситуации — административно в момент возникновения стандартной ситуации.

Маршрутизация в компьютерных сетях типично выполняется специальными программно-аппаратными средствами — маршрутизаторами ; в простых конфигурациях может выполняться и компьютерами общего назначения, соответственно настроенными.

Таким образом, графы окружают нас повсюду. Рассмотрим пример персонального компьютера: системный блок, клавиатура, компьютерная мышь, монитор, устройства звука и звукозаписи являются вершинами графа, а провода - его рёбрами.

Читайте также: