Основные виды графов. Примеры графов

ГРАФЫ

Графы возникли в восемнадцатом столетии, когда известный мате­матик, Леонард Эйлер, пытался решить теперь уже классическую задачу о Кенигсбергских мостах. В то время в городе Кенигсбер­ге было два oстровa, соединенных семью мостами с берегами реки Преголь и друг с другом так, как показано на рис. 7.1. 3адача со­стоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуться в то же место, откуда начиналась прогулка. Решая эту задачу, Эйлер изобразил Кенигсберг в виде графа, отождествив его вершины с частями города, а ребра - с мостами, которыми связаны эти части. Как мы покажем в § 7.1, Эйлеру удалось доказать, что искомого маршрута обхода города не существует.

Рисунок 7.1. Схема старого Кенигсберга

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

Графы и терминология

На рис. 7.1 изображены семь мостов Кенигсберга так. как они были расположены в восемнадцатом столетии. В задаче, к которой oбpa­тился Эйлер, спрашивается: можно ли найти маршрут прогулки, ко­торый проходит ровно один раз по каждому из мостов и начинается и заканчивается в одном и том же месте города?

Модель задачи - это граф, состоящий из множества вершин и множества ребер, соединяющих вершины. Вершины А, В, С и D символизируют берега реки и острова, а ребра а,в , c ,d, f и g обозначают семь мостов (см. рис. 7.2). Искомый маршрут (если он существует) соответствует обходу ребер графа таким образом, что каждое из них проходится только один раз. Проход ребра, очевидно, соответствует пересечению реки по мосту.

Рисунок 7.2. Модель задачи о мостах Кенигсберга

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

Кроме того, Эйлеру удалось доказать и противоположное утвер­ждение, так что граф, в котором любая пара вершин связана не­которой последовательностью ребер, является Эйлеровым тогда и только тогда, когда все его вершины имеют четную степень. Степенью вершины v называется число δ(v) ребер, ей инцидентных 2 .

Теперь совершенно очевидно, что в графе, моделирующем задачу о мостах Кенигсберга, эйлерова цикла найти нельзя. Действитель­но, степени всех его вершин нечетны: δ(B ) = δ(С) = δ(D) = 3 и δ(A ) = 5. С легкой руки Эйлера графы, подобные тому, который мы исследовали при решении задачи о мостах, стали использовать­ при решении многих практических задач, а их изучение выросло в значительную область математики.

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

Две вершины u и v в простом графе называются смежными , если они соединяются каким-то ребром е , про которое говорят, что оно инцидентно вершине u (и v). Таким образом, мы можем предста­влять себе множество Е ребер как множество пар смежных вершин, определяя тем самым нерефлексивное, симметричное отношение на множестве V. Отсутствие рефлексивности связано с тем, что в простом графе нет петель, т. е. ребер, оба конца которых находятся в одной вершине. Симметричность же отношения вытекает из того факта, что ребро е , соединяющее вершину и с v, соединяет и v с и (иначе говоря, ребра не ориентированы, т. е. не имеют направления). Единственное ребро простого графа, соединяющее пару вершин u и v, мы будем обозначать как иv (или vи).

Логическая матрица отношения на множестве вершин графа, котopoe задается его ребрами, называется ,матрицей смежности. Симметричность отношения в терминах матрицы смежности М озна­чает, что М симметрична относительно главной диагонали. А из-за нерефлексивности этого отношения на главной диагонали матрицы М стоит символ «Л».

Пример 7.1. Нарисуйте граф G(V, Е) с множеством вершин V = {а, Ь, с, d, е} и множеством ребер E = {ab, ae, bc, bd, ce, de}. Выпишите его матрицу смежности.

Решение. Граф G показан на рис. 7.3.

Рисунок 7.3.

Его матрица смежности имеет вид:

Для восстановления графа нам достаточно только тех элементов матрицы смежности, которые стоят над главной диагональю.

Подграфом графа G = (V, E) называется граф G’ = (V’, E’), в котором E’ C E и V’ C V.

Пример 7.2 Найдите среди графиков H, K и L, изображенных на рис. 7.4, подграфы графа G.

Решение. Обозначим вершины графов G, H и K как показано на рис. 7.5. Графы H и K – подграфы в G, как видно из наших обозначений. Граф L не является подграфом в G, поскольку у него есть вершина индекса 4, а у графа G такой нет.

Маршрутом длины k в графе G называется такая последовательность вершин v 0 , v 1 , …, v k , что для каждого i = 1, …, k пара v i – 1 v i образует ребро графа. Мы будем обозначать такой маршрут через v 0 v 1 … v k . Например 1 4 3 2 5 – это маршрут длины 4 в графе G из примера 7.2.

G H

K L

Рисунок 7.4.

Циклом в графе принято называть последовательность вершин v 0 , v 1 , … , v k , каждая пара которых является концами одного ребра, причем v 0 = v 1 , а остальные вершины (и ребра) не повторяются. Иными словами, цикл – это замкнутый маршрут, проходящий через каждую свою вершину и ребро только один раз

1 2 1 2 3

Рисунок 7.5

Пример 7.3. Найдите циклы в графе G из примера 7.2.

Решение. В этом графе есть два разных цикла длины 5:

1 3 2 5 4 1 и 1 2 5 4 3 1

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

1 2 5 4 1, 1 2 3 4 1 и 2 5 4 3 2,

и два цикла длины 3:

1 2 3 1 и 1 3 4 1.

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

Граф, называют связным, если любую пару его вершин соединяет какой – нибудь маршрут. Любой общий граф можно разбить на подграфы, каждый из которых окажется связным. Минимальное число таких связных компонент называется числом связности графа и обозначается через c (G ) . Вопросы связности имеют важное значение в приложениях теории графов к компьютерным сетям. Следующий алгоритм применяется для определения числа связности графа.

Алгоритм связности.

Пусть G = (V, E) – граф. Алгоритм предназначен для вычисления значения c = c (G ), т.е. числа компонент связности данного графа G.

V’ :=V;

while V’≠ ø do

Выбрать y Є V ’

Найти вершины, соединяющие маршрутом с у;

Удалить вершину у из V ’ и

соответствующие ребра из Е;

c := c +1;

Пример 7.4. Проследите за работой алгоритма связности на графе, изображенном на рис. 7.6.

Рисунок 7.6.

Решение. Смотри табл. 7.1.

Таблица 7.1.

Исходные значения	{1,2,3,4,5,6,7,8}
Выбор у = 1
Выбор у = 2
Выбор у = 7

Итак, c (G ) = 3. Соответствующие компоненты связности приведены на рис. 7.7.

5

Основные вопросы:

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

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

История возникновения графов

Впервые основы теории графов
появились в работах Леонарда
Эйлера (1707-1783;
швейцарский, немецкий и
российский математик) , в
которых он описывал решение
головоломок и математических
развлекательных задач.
Теория графов началась с
решения Эйлером задачи о
семи мостах
Кёнигсберга.

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

История возникновения графов

Термин "граф" впервые появился в книге
венгерского математика Д. Кенига в 1936 г., хотя
начальные важнейшие теоремы о графах
восходят к Л. Эйлеру.

В основе теории лежит понятие графа.

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

Состав графа

Граф состоит из вершин, связанных линиями. Вершины
графа обозначают латинскими буквами A, B, C, D или
цифрами.
Направленная линия (со стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется ребром.
Линия, выходящая из некоторой вершины и входящая в
неё же, называется петлей.
дуга
А
ребро
В
петля
С

Ориентированный граф -

граф, вершины которого соединены дугами. С
помощью таких графов могут быть представлены
схемы односторонних отношений.
Юра
Аня
Маша
Коля
Витя

Взвешенный граф

Это граф, рёбрам или дугам которого поставлены
в соответствие числовые величины (они могут
обозначать, например, расстояние между городами
или стоимость перевозки).
Вес графа равен сумме весов его рёбер.
4
B
C
2
3
2
A
1
E
D
A
B
C
D
Е
A B C D Е
3 1
4
2
3 4
2
1
2 2
Таблице (она называется весовой
матрицей) соответствует граф.

Если
ребро графа G соединяет две его
вершины V и W, (т.е. V ,W X), то говорят,
что это ребро им инцидентно.
Две вершины графа называются смежными,
если существует инцидентное им ребро: на
рисунке смежными являются вершины А и В,
А и С.
А
С
В

Если граф G имеет ребро, у которого начало
и конец совпадают, то это ребро называется
петлёй. На рисунке ребро q(С, С) – петля.
q
E
С
A
D
B

Два ребра называются смежными, если они
имеют общую вершину.
На рисунке смежными являются, например,
рёбра х1 и х2 с общей вершиной С.
D
х5
х1
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

Рёбра, которые начинаются в одной и
той же вершине, заканчиваются также
в одной и той же вершине, называются
кратными, или параллельными.
Количество одинаковых пар вида
(V , W) называется кратностью ребра (V , W)
Число рёбер, инцидентных вершине А,
называется степенью этой вершины и
обозначается deg(A) (от англ. degree –
степень).

На рисунке кратными являются, например,
рёбра х1(А, В), х2(А, В). Вершинам А и С
инцидентны рёбра х3, х4, х5. Следовательно,
ребро АС имеет кратность, равную 3, а ребро
АВ – кратность, равную 2.
А
х4
х1
х3
С
х2
х5
В

На рисунке вершина А имеет степень,
равную 1, вершина С – 4, вершина D – 2.
Записывается это в виде: deg(A)=1, deg(C)=4,
deg(D)=2.
D
х5
х1
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

Вершина графа, имеющая степень, равную нулю,
называется изолированной.
Граф, состоящий из изолированных вершин,
называется нуль-графом.
Вершина графа, имеющая степень, равную 1,
называется висячей.
Граф, не имеющий ребер (дуг), называется
пустым.
E
C
A
D
B
На рисунке вершина
Е – изолированная:
deg(E)=0.

На рисунке вершины А, В, Е, G, H – висячие.
D
х5
х1
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

Теорема 1. В графе G V , X сумма
степеней всех его вершин – число чётное,
равное удвоенному числу рёбер графа:
n
deg(V) 2m
i 1
i
Количество ребер в любом графе равно
половине суммы степеней его вершин.
где n V
- число вершин;
m X - число рёбер графа.

Вершина называется чётной (нечётной),
если её степень – чётное (нечётное) число.
На рисунке deg(D)=2, deg(F)=3, значит у
графа вершина D является чётной, а F –
нечётной.
х5
D
х1
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

Задача. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью

другими?

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

Задача. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 - по 4 друга, а 10 - по 5 друзей?

Дополнением графа G V , X называется
граф G V , X с теми же вершинами V, что и
граф G, и имеющий те и только те рёбра X ,
которые необходимо добавить к графу G, чтобы он
стал полным. На рисунке дополнением графа G1 до
графа G является граф
G1
G
G1
G1

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

Закономерность 3.
Закономерность 4.
Число нечетных
Невозможно
вершин любого
графа четно.
начертить граф с
нечетным числом
нечетных вершин.

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

Закономерность 7.
Граф, имеющий более
двух нечетных
вершин, невозможно
начертить «одним
росчерком». Фигура
(граф), которую можно
начертить не отрывая
карандаш от бумаги,
называется
уникурсальной.

Пути и маршруты в графах

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

В качестве примера рассмотрим орграф,
представленный на рисунке. Одним из существующих
путей, соединяющих вершины 1 и 3, является
последовательность вершин 1, 2, 1, 4, 3. Единственным
простым путем для той же пары вершин является
последовательность 1, 4, 3. Пути из вершины 1 в
вершину 5 для того же графа не существует.

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

Путь называется замкнутым, если
начальная и конечная вершины совпадают.
Замкнутый путь называется циклом, если все
его вершины (кроме начальной и конечной)
различны.
Рассмотрим граф. Для него путь 2, 1, 6, 5, 4, 1,
2 является замкнутым; а путь 1, 6, 5, 4, 1
является циклом.

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

На рисунке HCDFD – маршрут длиной 4.
Обозначение: |HCDFD|=4. Маршрут принято
задавать
как
последовательность
рёбер,
поскольку это удобно при наличии кратных
рёбер.
х
D
х1
5
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

В графе на рисунке (t, s, p, r), (u, s, t, r) – циклы
длиной 4, (r, t, q, s, u) – цикл длиной 5, (t, s, u, r, t, s, p, r)
– 8-цикл, (p, u) – 2-цикл, петля (q) – 1-цикл.
E
q
C
s
A
p
t
D
r
B
u

Операции над графами

Одноместные операции
1. Удаление ребра графа - при этом все вершины графа
сохраняются
2. Добавление ребра графа между двумя
существующими вершинами.
3. Удаление вершины (вместе с инцидентными
ребрами).
4. Добавление вершины (которую можно соединить с
некоторыми вершинами графа).
5. Стягивание ребра - отождествление пары вершин, т.е.
удаление пары смежных вершин, и добавление новой
вершины, смежной с теми вершинами, которые были
смежны, хотя бы одной из удаленных вершин)
6. Подразбиение ребра с- удаление ребра и добавление
новой вершины, которая соединяется ребром с каждой из
вершин удаленного ребра.

Операции над графами

Двуместные операции
Объединением графов G1 (V1 , X 1) и G2 (V2 , X 2)
называется граф G G1 G2 , множество вершин
которого V V1 V2 , а множество рёбер X X 1 X 2 .
Пересечением графов G1 и G2 называется
граф G G1 G2 , для которого X X 1 X 2 множество рёбер, а V V1 V2 - множество вершин.
Кольцевой суммой двух графов называется граф
G G1 G2 , порождённый множеством вершин
т.е.
V V1 V2 и множеством рёбер (X1 X 2) \ (X1 X 2) ,
множеством рёбер, содержащихся либо в G1 , либо в
G2 , но не в G1 G2 .

V4
V2
х3
х2
V3
х4
V1
х1
V5
х2
х7
х3
х4
х4
V1
х7
V1
G=G1UG2
V3
х4
V5
х2
V1
х3
G=G1∩G2
V2
х1
G2
V4
V2
х5 х6
х6
V3
V1
V4
V3
V4
х5
х3
х1
G1
V2
V5
V2
V4
х5 х6V
3
х7
G=G1 G2

Применение графов

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

Применение графов

Лабиринт - это граф. А исследовать его - это найти
путь в этом графе.
дальше

Использует графы и
дворянство.
На рисунке приведена
часть генеалогического
дерева
знаменитого
дворянского рода Л. Н.
Толстого. Здесь его
вершины – члены этого
рода, а связывающие их
отрезки – отношения
родственности,
ведущие от родителей к
детям.
дальше

Применение графов

Графами являются блок – схемы программ для
ЭВМ.
дальше

Применение графов

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

Применение графов

Типичными графами на картах города
являются схемы движения городского
транспорта.
дальше

Выводы

Графы – это замечательные математические
объекты, с помощью, которых можно решать
математические, экономические и логические
задачи. Также можно решать различные
головоломки и упрощать условия задач по
физике, химии, электронике, автоматике. Графы
используются
при
составлении
карт
и
генеалогических древ.
В математике даже есть специальный раздел,
который так и называется: «Теория графов».
содержание

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом . (рис.2 )

Графы, в которых не построены все возможные ребра, называются неполными графами . (рис.3 )

Графы, в которых построены все возможные ребра, называются полными графами . (рис.4 )


Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным .

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

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

Степени вершин и подсчет числа ребер.

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

Если степени всех вершин графа равны, то граф называется однородным . Таким образом, любой полный граф - однородный.

На рисунке 5 изображен граф с пятью вершинами.

Степень вершины А обозначим Ст.А.

На рисунке:
Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа.

Число нечетных вершин любого графа четно .

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2.

Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.

Эйлеровы графы.

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

Такими графы названы в честь учёного Леонарда Эйлера .


Закономерность 3. (вытекает из рассмотренной нами теоремы).
Невозможно начертить граф с нечетным числом нечетных вершин.

Закономерность 4. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.

Закономерность 5. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.

Закономерность 6. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком ».

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

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

На рисунке 7, очевидно, изображен несвязный граф.

Граф называется несвязным , если это условие не выполняется.

Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным.(рис.8 )

Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом .

Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа. (рис.8 )

Несвязный граф состоит из нескольких «кусков ». Эти «куски» называются компонентами связности графа. Каждая компонента связности является, конечно, связным графом. Отметим, что связный граф имеет одну компоненту связности.

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

Деревья.

Деревом называется любой связный граф, не имеющий циклов.

Циклом называется путь, в котором совпадают начало с концом.

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом.

Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.9а ).

В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5.

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

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

Висячей вершиной называется вершина, из которой выходит ровно одно ребро (рис.10 ).
(кружком обведены висячие вершины).


Для каждой пары вершин дерева существует единственный путь, их соединяющий .

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

Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается » на два дерева.

Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом .

(о висячей вершине). В каждом дереве есть висячая вершина.

. В дереве число вершин на одну больше числа ребер.

Изоморфизм. Плоские графы и теорема Эйлера.

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

Докажем, что графы изображенные на рисунке 11 изоморфны.


Пронумеруем вершины первого и второго графов от 1 и до 4 (рис.12 ).


В первом графе соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4; заметим, что во втором графе также соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4, следовательно, данные графы изоморфны.

Для того, чтобы выяснить, изоморфны ли два графа, нужно убедиться в том, что у них:

• одинаковое количество вершин
• если вершины одного графа соединены ребром, то и соответствующие им вершины другого графа тоже соединены ребром.

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

Эйлера. Для правильно нарисованного связного плоского графа имеет равенство: V-E+F=2, где V – число вершин, E - число рёбер, F – число кусков.(равенство V -E+F=2 обычно называют формулой Эйлера) .

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

Понтрягина – Куратовского . Граф является плоским тогда и только тогда, когда он не содержит (в топологическом смысле) графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами.

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

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

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

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

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

Граф, на рёбрах которого расставлены стрелки, называется ориентированным .

Степенью выхода вершины ориентированного графа называется число ребер, для которых эта вершина является началом (число ребер, «выходящих » из вершины).

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

Так, на рисунке 15 изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие:
Ст.вх.А=2, Ст.вых.А=1 Ст.вх.В=2, Ст.вых.В=0 Ст.вх.Д=1, Ст.вых.Д=3.

Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер A1A2, A2A3, ..., Аn-1Аn, в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз.

На рисунке.15 показаны примеры путей в ориентированном графе. Причем, первые два пути простые - ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым,т. к. через вершину Г путь «проходил » дважды.

Ориентированным циклом называется замкнутый путь в ориентированном графе.

На рисунке 15 приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути.

Так, на рисунке 16 пути от А к Д могут быть различны и иметь различную длину.
Первый путь имеет длину 2, второй - 3,
а третий - 4.

Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними. Так расстояние между вершинами А и Д на графе рисунка 16 равно 2; записывают так: S(АД)=2.

Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным(обозначают значком бесконечности). Так, расстояние между вершинами Б и Д графа, представленного на рисунке 17 бесконечно: S(БД) = ∞

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

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

ВВЕДЕНИЕ

«В математике следует помнить не формулы, а процесс мышления…»

Е. И. Игнатьев

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

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

Цель определила следующие задачи:

познакомиться с историей теории графов;

изучить основные понятия теории графов и основные характеристики графов;

показать практическое применение теории графов в различных областях знаний;

рассмотреть способы решения задач с помощью графов и составить собственные задачи.

Объект исследования: сфера деятельности человека на предмет применения метода графов.

Предмет исследования: раздел математики «Теория графов».

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

Методы исследовательской работы:

В ходе нашего исследования были использованы такие методы, как:

1) Работа с различными источниками информации.

2) Описание, сбор, систематизация материала.

3) Наблюдение, анализ и сравнение.

4) Составление задач.

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

ГЛАВА I. ТЕОРЕТИЧЕСКИЙ ОБЗОР МАТЕРИАЛА ПО ТЕМЕ ИССЛЕДОВАНИЯ

1. Теория графов. Основные понятия

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

В математике определение графа дается так:

Термин «граф» в математике определяется следующим образом:

Граф - это конечное множество точек - вершин , которые могут быть соединены линиями - ребрами .

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

Рис. 1 Примеры графов

Число ребер, которое принадлежит одной вершине, называется степенью вершины графа . Если степень вершины нечетное число, вершина называется - нечетной . Если степень вершины число четное, то и вершина называется четной .

Рис. 2 Вершина графа

Нуль-граф - это граф, состоящий только из изолированных вершин, не соединенных ребрами.

Полный граф - это граф, каждая пара вершин которого соединена ребром. N-угольник, в котором проведены все диагонали, может служить примеров полного графа.

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

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

Если граф связанный, но не содержит циклов, то такой граф называетсядеревом .

1. Характеристики графов

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

Длина кратчайшей цепи из вершин a и b называется расстоянием между вершинами a и b.

Вершина а называется центром графа, если расстояние между вершиной а и любой другой вершиной является наименьшим и из возможных. Такое расстояние есть радиус графа.

Максимально возможное расстояние между двумя любыми вершинами графа называется диаметром графа.

Раскраска графов и применение.

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

В 1852 году английскому студенту Френсису Гутри поставили задачу раскрасить карту Великобритани, выделив каждое графство отдельным цветом. Из-за небольшого выбора красок Гутри использовал их повторно. Он подбирал цвета так, чтобы те графства, которые имеют общий участок границы, обязательно окрашивались в разные цвета. Возник вопрос, какое наименьшее количество красок необходимо для раскрашивания различных карт. Френсис Гутри предположил, хотя и не смог доказать, что четырех цветов будет достаточно. Эта проблема бурно обсуждалась в студенческих кругах, но позже была забыта.

«Проблема четырех красок» вызывала все больший интерес, но так и не была решена, даже выдающимися математиками. В 1890 году английским математиком Перси Хивудом было доказано, что для раскрашивания любой карты будет достаточно пяти красок. А только 1968 году смогли доказать, что для раскрашивания карты, на которой изображено меньше сорока стран, будет достаточно 4 цветов.

В 1976 году эта задача была решена при использовании компьютера двумя американскими математиками Кеннетом Аппелем и Вольфгантом Хакеном. Для ее решения все карты были поделены на 2000 типов. Для компьютера была создана программа, которая исследовала все типы с целью выяления таких карт, для раскрашивания которых будет недостаточно четырех красок. Только три типа карт компьютер исследовать не смог, поэтому математики изучали их самостоятельно. В результате было установлено, что для раскрашивания всех 2000 типов карт будет достаточно 4 красок. Им было объявлено о решении проблемы четырех красок. В этот день почтовое отделение при университете, в котором работали Аппель и Хакен на всех марках ставило штемпель со словами: «Четырех красок достаточно».

Можно представить задачу о четырех красках несколько иначе.

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

Эйлеровы и Гамильтоновы графы

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

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

На реке Прегель расположен город Калининград (бывший Кенигсберг). Река омывала два острова, которые между собой и с берегами были соединены мостами. Старых мостов сейчас уже нет. Память о них осталась только на карте города.

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

При решении задачи про мосты Кенигсберга Эйлеру удалось сформулировать свойства графов.

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

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

Если есть граф с числом нечетных вершин больше двух, то граф невозможно начертить одним росчерком.

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

Если граф имеет цикл (не обязательно простой), содержащий все рѐбра графа по одному разу, то такой цикл называется Эйлеровым циклом . Эйлерова цепь (путь, цикл, контур) — цепь (путь, цикл, контур), содержащая все рѐбра (дуги) графа по одному разу.

ГЛАВА II. ОПИСАНИЕ ИССЛЕДОВАНИЯ И ЕГО РЕЗУЛЬТАТЫ

2.1. Этапы проведения исследования

Для проверки гипотезы исследование включало три этапа (таблица 1):

Этапы исследования

Таблица 1.

		Используемые методы
Теоретическое исследование проблемы	Изучить и проанализировать познавательную и научную литературу.	 самостоятельное размышление;  изучение информационных источников;  поиск необходимой литературы.
Практическое исследование проблемы	Рассмотреть и проанализировать области практического применения графов;	 наблюдение;  анализ;  сравнение;  анкетирование.
3 этап. Практическое использование результатов	Обобщить изученную информацию;	 систематизация;  отчет (устный, письменный, с демонстрацией материалов)	сентябрь 2017 г.

2.2. Области практического применения графов

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

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

Например, если нужно закодировать некоторое число сообщений в виде определенных последовательностей нулей и единиц различной длины. Код считается наилучшим, для заданной вероятности кодовых слов, если средняя длина слов наименьшая в сравнении другими распределениями вероятности. Для решения такой задачи Хаффман предложил алгоритм, в котором, код представляется деревом-графом в рамках теории поиска. Для каждой вершины предлагается вопрос, ответом на который может быть либо, «да», либо «нет» - что соответствует двум ребрам, выходящим из вершины. Построение такого дерева завершается после установления того, что требовалось. Это может применяться в интервьюировании нескольких человек, когда заранее неизвестен ответ на предыдущий вопрос, план интервью представляется в виде двоичного дерева.

Графы и химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:

CnH 2n+2

Все атомы углеводорода 4-хвалентны, все атомы водорода 1-валентны. Структурные формулы простейших углеводородов показаны на рисунке.

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

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

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

Графы и физика

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

Итак, все выше сказанное подтверждает практическую ценность графов.

Математика интернета

Интернет - всемирная система объединенных компьютерных сетей для хранения и передачи информации.

Сеть интернет можно представить в виде графа, где вершины графа - это интернет сайты, а ребра - это ссылки (гиперссылки), идущие с одних сайтов на другие.

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

Веб-граф разрежен. Он содержит всего лишь в несколько раз больше ребер, чем вершин.

Несмотря на разреженность, интернет очень тесен. От одного сайта до другого по ссылкам, можно перейти за 5 - 6 кликов (знаменитая теория «шести рукопожатий»).

Как мы знаем, степень графа - это число ребер, которым принадлежит вершина. Степени вершин веб-графа распределены по определенному закону: доля сайтов (вершин) с большим количеством ссылок (ребер) мала, а сайтов с малым количеством ссылок - велика. Математически это можно записать так:

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

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

Интернет как целое устойчив к случайным атакам на сайты.

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

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

Эта задача пока полностью не решена! Решение этой задачи - построения качественной модели интернета - позволит разработать новые инструменты для улучшения поиска информации, выявления спама, распространения информации.

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

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

г. Мурманск с помощью графа.

Когда человек приезжает в новый для него город, как правило, первое желание - это посетить главные достопримечательности. Но при этом запас времени зачастую ограничен, а в случае деловой поездки, совсем мал. Следовательно, необходимо планировать знакомство с достопримечательностями заранее. И в построении маршрута отлично помогут графы!

В качестве примера рассмотрим типичный случай прибытия в Мурманск из аэропорта в первый раз. Планируется посетить следующие достопримечательности:

1. Морской православный храм Спас-на-водах;

2. Свято-Никольский собор;

3. Океанариум;

4. Памятник коту Семену;

5. Атомный ледокол Ленин;

6. Парк Огни Мурманска;

7. Парк Долина Уюта;

8. Кольский мост;

9. Музей истории Мурманского морского пароходства;

10. Площадь Пяти углов;

11. Морской торговый порт

Вначале расположим эти места на карте и получим наглядное представление о местоположении и расстоянии между достопримечательностями. Сеть дорог достаточно развита, и перемещение на автомобиле не будет затруднительным.

Достопримечательности на карте (слева) и полученный граф (справа) показаны на соответствующем рисунке ПРИЛОЖЕНИЯ №1. Таким образом, новоприбывший вначале проедет около Кольского моста(и, при желании может пересечь его туда - обратно); затем отдохнет в Парке Огни Мурманска и Долине Уюта и отправится дальше. В итоге оптимальный маршрут составит:

С помощью графа можно также визуализировать схему проведения соцопросов. Примеры представлены в ПРИЛОЖЕНИИ №2. В зависимости от данных ответов опрашиваемому задают разные вопросы. Например, если в социологическом опросе №1 опрашиваемый считает математику важнейшей из наук, у него спросят, уверенно ли он чувствует себя на уроках физики; если же он считает иначе, второй вопрос будет касаться востребованности гуманитарных наук. Вершинами такого графа являются вопросы, а ребрами - варианты ответов.

2.3. Применение теории графов при решении задач

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

Задача №1.

Пятеро одноклассников, на встрече выпускников, обменялись рукопожатиями. Сколько всего было сделано рукопожатий?

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

Ответ: 10 рукопожатий (каждая линия означает одно рукопожатие).

Задача №2.

У моей бабушке в деревне, возле дома растут 8 деревьев: тополь, дуб, клен, яблоня, лиственница, береза, рябина и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. В какой последовательности расположатся деревья по высоте от самого высокого к самому низкому.

Решение:

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

Ответ: клен, яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Задача №3.

У Мамы есть 2 конверта: обычный и авиа, и 3 марки: квадратная, прямоугольная и треугольная. Сколькими способами Мама может выбрать конверт и марку, чтобы отправить письмо Папе?

Ответ: 6 способов

Задача №4.

Между населенными пунктами A, B, C, D, E построены дороги. Нужно определить длину кратчайшего пути между пунктами А и Е. Передвигаться можно только по дорогам, длина которых указана на рисунке.

Задача №5.

Тремя одноклассника - Максим, Кирилл и Вова решили заняться спортом и прошли отбор спортивные секции. Известно, что в баскетбольную секцию претендовал 1 мальчик, а в хоккей хотели играть трое. Максим пробовался только в 1 секцию, Кирилл отбирался во все три секции, а Вова в 2. Кого из мальчиков в какую спортивную секцию отобрали?

Решение: Для решения задачи применим графы

Баскетбол Максим

Футбол Кирилл

Хоккей Вова

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

Задача №6.

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

1. Преподаватель ОБЖ согласен дать только последний урок;

2. Преподаватель географии может дать либо второй, либо третий урок;

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

4. Преподаватель физики может дать либо первый, либо второй, либо третий уроки, но только в одном классе.

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

Решение: Эту задачу можно решить перебирая все возможные варианты, но проще, если начертить граф.

1. 1) физика 2. 1) математика 3. 1) математика

2) математика 2) физика 2) география

3) география 3) география 3) физика

4) ОБЖ 4) ОБЖ 4) ОБЖ

Заключение

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

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

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

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

Таким образом, цель исследовательской работы достигнута, задачи решены. В перспективе мы планируем продолжить изучение теории графов и разработать свои маршруты, например, с помощью графа создать экскурсионный маршрут для школьного автобуса ЗАТО Александровск по музеям и памятным местам г. Мурманска.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

Березина Л. Ю. «Графы и их применение» - М.: «Просвещение», 1979

Гарднер М. «Математические досуги», М. «Мир», 1972

Гарднер М. «Математические головоломки и развлечения», М. «Мир», 1971

Горбачев А. «Сборник олимпиадных задач» - М. МЦНМО, 2005

Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664

Касаткин В. Н. «Необычные задачи математики», Киев, «Радяньска школа», 1987

Математическая составляющая / Редакторы-составители Н.Н. Андреев, С.П. Коновалов, Н.М. Панюшкин. - М.: Фонд «Математические этюды» 2015 г. - 151 с.

Мельников О. И. «Занимательные задачи по теории графов», Мн. «ТетраСистемс»,2001

Мельников О.И. Незнайка в стране графов: Пособие для учащихся. Изд. 3-е, стереотипное. М.: КомКнига, 2007. — 160 с.

Олехник С. Н., Нестеренко Ю. В., Потапов М. К. «Старинные занимательные задачи», М. «Наука», 1988

Оре О. «Графы и их применения», М. «Мир», 1965

Харари Ф. Теория графов / Пер.с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. - 296 с.

ПРИЛОЖЕНИЕ №1

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

г. Мурманск с помощью графа.

Оптимальный маршрут составит:

8. Кольский мост6. Парк Огни Мурманска7. Парк Долина Уюта2. Свято-Никольский собор10. Площадь Пяти углов5. Атомный ледокол Ленин9. Музей истории Мурманского морского пароходства11. Морской торговый порт1. Морской православный храм Спас-на-водах4. Памятник коту Семену3. Океанариум.

ПУТЕВОДИТЕЛЬ ПО ДОСТОПРИМЕЧАТЕЛЬНОСТЯМ МУРМАНСКА

ПРИЛОЖЕНИЕ №2

Социологические опросы № 1, 2

Рис. 7.1

II. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

§ 7. Основные определения и типы графов

1. Основны е понятия

Пусть V – конечное непустое множество и Е {{u , v } u ,v V , u ≠ v } – множество его двухэлементных подмножеств. Пара G = (V, E ) называется графом . Множество V = V (G ) при этом называется множеством вершин графа G, а его элементы – вершинами; множество Е = Е (G ) называется множеством ребер графа G , а его элементы – ребрами. И вершины, и ребра графа G называются его элементами. Поэтому если u – вершина графа G , а е – ребро G , то вместо u V (G ), e E (G ) можно писать u G , e G .

Если e = {u , v } – ребро графа G (пишут также е = uv ), то вершины u и v называются концами ребра е .

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

Вершины u и v графа G называется смежными , если {u , v } E (G ), т.е. если они соединены ребром. Два ребра, в свою очередь, называются смежными , если они имеют общий конец. Если вершина v является концом ребра e , то v

и e называются инцидентными .

Мощность V (G ) множества вершин V (G ) называется порядком графа G и обозначается G . Если V (G ) = n и E (G ) =m , то граф G называется (n,m ) -графом .

2. Основные типы графов

Граф называется пустым , если E (G) = , т.е., если в нем нет ребер. Пустой граф порядка n обозначается 0 n . Граф 0 1 называется тривиальным . Граф, в котором любые две вершины соединены ребром, называется полным . Полный граф порядка n обозначается K n (рис. 7.2 – 7.5).

Граф такого вида, как на рис. 7.6, называется простой цепью . Простая цепь порядка n обозначается P n (на рис. 7.6 изображена цепь P 4 ). Простая цепь P n имеет n – 1 ребер.

Рис. 7.9

Замкнутые цепи, т.е. такие графы как на рис. 7.7, называются простыми циклами . Простой цикл порядка n обозначается C n (на рис. 7.7 изображена простая цепь С 7 ). Понятно, что простая цепь C n имеет столько же ребер, сколько и вершин, т.е. n .

Графы, такие как на рис. 7.8, называются колесами. Колесо порядка n +1 обозначается W n (на рис. 7.8 изображено колесо W 7 ); оно имеет 2n ребер.

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

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

Полный двудольный граф с n вершинами в одной доле и с m вершинами – в другой обозначается K n,m . См. примеры, приведенные на рис. 7.10 – 7.12.

	K 2,2		K 2,3		K 3,3

Графы K 1, n называется звездными графами, или звездами.

Легко видеть, что граф K n,m является (n+m, nm )- графом, т.е. имеет n+m вершин и nm ребер.

Понятно, что существуют графы, которые можно одновременно отнести к нескольким типам. Например, K 3 = C 3 , K 2 = P 2 , K 2, 2 = C 4 , K 4 = W 3 .

3. Обобщения понятия графа

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

Рис. 7.16

когда необходимо допускать существование нескольких ребер между одной и той же парой вершин. Такие ребра называются кратными . Граф с кратными ребрами называется мультиграфом (рис. 7.14). Графы, соответствующие исходному определению (в тех случаях, когда нужно подчеркнуть, что в них отсутствуют кратные ребра), называются простыми графами (рис. 7.13). Кроме того, порой приходится рассматривать ребра вида {v, v }, соединяющие вершину v саму с собой. Такие ребра называются петлями . Мультиграф с петлями называется псевдографом (рис. 7.15.).

Пара (V , E ), где V – непустое множество, а E V 2 , называется ориентированным графом (или кратко: орграфом ). Ребра такого графа представляют собой ориентированные (т.е. упорядоченные) пары вида

(u , v ). При этом, вершина u называется началом ребра , а v – концом . Ориентированные ребра называются дугами и изображаются в виде линий со стрелками, указывающими направление от начала ребра к концу

Дуги (u , v ) и (v , u ), соединяющие одну и ту же пару вершин, но имеющие противоположные направления, называются симметричными .

Можно рассматривать не только простые орграфы, но также ориентированные мульти- и псевдографы.

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

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

4. Изоморфные графы

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

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

Определение . Два графа G и H называются изоморфными , если существует биекция f : V (G ) → V (H ), сохраняющая смежность, т.е. такое биективное отображение, при котором образы вершин v и u графа G смежны в H тогда и только тогда, когда u и v смежны в графе G . Отображение f , обладающее указанным свойством, называется

изоморфизмом.

Если графы G и H изоморфны, то пишут G H .

Например, все три графа на рис. 7.17-7.19 изоморфны друг другу (изоморфизм определяется нумерацией вершин).

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

В некоторых ситуациях все же приходится различать изоморфные графы и тогда возникает понятие "помеченный граф ". Граф порядка n называется помеченным, если его вершинам присвоены метки, например, номера 1, 2, 3, …, n . В этом случае вершины графа G отождествляют с их номерами, т.е. полагают, что V (G ) = {1, 2, 3, …, n }.