Ученики на Учителя.com


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

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ И НАУКИ КЕМЕРОВСКОЙ ОБЛАСТИ
Государственное образовательное учреждение среднего профессионального
образования
Кемеровский профессионально-технический техникум
Элементы теории графов.
(статья)
Подготовил преподаватель математики
Валеева Людмила Леонидовна
Кемерово 2015
Граф — основной объект изучения математической теории графов,
совокупность непустого множества вершин и наборов пар вершин (связей
между вершинами).
Объекты представляются как вершины, или узлы графа, а связи — как
дуги, или рёбра
[1]
. Для разных областей применения виды графов могут
различаться направленностью, ограничениями на количество связей и
дополнительными данными о вершинах или рёбрах.
Многие структуры, представляющие практический интерес в математике
и информатике, могут быть представлены графами. Например,
строение техникума можно смоделировать при помощи ориентированного
графа, в котором вершины — это кабинеты, а дуги (ориентированные рёбра) —
студенты.
Определение 1. Мы говорим, что задан граф, если даны:
1) некоторое конечное множество Х, элементы которого изображены точками;
эти элементы могут обозначать людей, предметы, события, состояния и т. д.;
2) некоторое множество U упорядоченных или неупорядоченных пар (а,b),
причем а
Х, b
X; каждая подобная пара соответствует на схеме линии (связи),
соединяющей точки а и b (если пара упорядочена, то направление связи
указано стрелкой).
[1]
При этом точки а и b могут иметь и более одной связи. Если для данной
пары (а, b) имеется r (r > 1) таких связей, то их различают с помощью
индексов, например, (а, b)
1
, (а, b)
2
,. . . ,(а, b)
r
.
Множества X и U определяют граф G = [X, U]. Граф называется
направленным, если элементы множества U являются упорядоченными парами
точек (см. рис. 1), и ненаправленным — в противном случае.
Рис. 1.
Рис.1
Определение 2. Две вершины называются связанными, если они
соединены ребром. Говорят, что вершина инцидентна ребру, если она служит
концом этого ребра.
Определение 3. Если данная вершина инцидентна в G ровно r ребрам, то r
называется связностью данной вершины в G.
В дальнейшем под графом мы будем понимать ненаправленный граф;
рассматривая направленный граф, мы каждый раз будем особо это оговаривать.
Иногда в графах бывают вершины, не инцидентные ни одному ребру.
Такие вершины называются изолированными.
Мы будем рассматривать лишь конечные графы, содержащие конечное
множество вершин и конечное множество ребер.
Рис. 2.
Определение 4. Граф G называется простым, если он не содержит
дублирующихся ребер, то есть любые две вершины в G связаны не более чем
одним ребром (на рисунке 2 имеются дублирующие ребра).
[2]
Некоторые теоремы и их применения
Рис. 3.
M
5
M
6
M
3
M
2
M
1
M
4
Теорема 1. Пусть /Х/ = n – число вершин, |U| – число ребер и s
1
, s
2
, . . . ,
s
n
– связности вершин графа G = [X, U]. Тогда
n
i
i
Us
1
2
,(1) то есть сумма
связностей всех вершин графа G вдвое больше числа его ребер.
Рис. 3
Доказательство. Заменим каждое ребро двумя половинками (рис. 3).
Тогда каждой половинке ребра будет инцидентна одна и только одна вершина.
Если вершина а
i
Х имеет связность s
i
, то она инцидентна ровно s
i
половинкам
ребер; значит, сумма
n
i
i
s
1
равна числу всех полуребер или, что то же самое,
удвоенному числу ребер.
Определение 5. Последовательность ребер, в которой каждое ребро графа
G встречается не более одного раза, называется цепочкой.
Примечание. Одни и те же вершины могут встречаться в цепочке и более
одного раза.
Определение 6. Открытая цепочка, в которой каждая вершина встречается
не более одного раза, называется путем.
Определение 7. Замкнутая цепочка, в которой каждая вершина
встречается не более одного раза, называется кольцом.
Определение 8. Граф G, в котором каждые две вершины а
i
и а
j
связаны не
менее чем одним путем, называется связным.
Теорема 2. В каждом связном графе G число вершин нечетной связности
четно.
Рис. 5.
Доказательство. Обозначим сумму связностей «нечетных» вершин (то
есть сумму нечетных слагаемых в формуле (1)) через
1
, а сумму связностей
«четных» вершин (то есть сумму четных слагаемых в (1)) через
2
. Тогда по
теореме 1
||2
||
1
21
Us
X
i
i
,откуда
21
||2 U
. (2)
Числа 2|U| и
2
, а следовательно, и их разность, стоящая в правой части
равенства (2), четны, а потому и левая часть (сумма нечетных слагаемых —
1
) — число четное. Далее легко доказать (от противного), что количество
(нечетных!) слагаемых в этой сумме — четное. Теорема доказана.
[1]
Информационное обеспечение
1. Baker, M., Norine, N. Riemann-Roch and Abel-Jacobi theory on a finite graph.
[Text] / M. Baker, N. Norine/ New York: Advances in Mathematics, 2007. –
p. 766-788.
2. Nagnibeda, T. The Jacobian of a finite graph, in: Harmonic Functions on Trees
and Buildings. [Text] / T. Nagnibeda. New York: Contemp. Math., 1997. - pp.
149–151.
Периодические издания (отечественные журналы):
1. Математика [Текст] : методический журнал для учителей математики /
учредитель ООО «Чистые пруды». - . - Москва : ИД «Первое сентября»,
2010 - . - Ежемес. - [http://mat.lseptember.ru/].
2. Научные исследования в образовании [Текст] : приложение к журналу
«Профессиональное образование. Столица» / учредители Департамент
образования города Москвы; Российская академия образования;
Академия профессионального образования. – 2006 – . – Москва :
НИИРПО, 2012 – . – Ежемес.
3. Образование. Карьера. Общество [Текст] : учредитель ГОУ «Кузбасский
региональный институт развития профессионального образования». –
2005 -.- Кемерово : ГОУ « КРИРПО», 2010 -.- Ежеквар. -
[http://www.krirpo.ru/].
4. Профессиональное образование. Столица [Текст]: информационно-
педагогическое, научно-методическое издание / учредители
Департамент образования города Москвы; Российская академия
образования; Академия профессионального образования. – 1997 – . –
Москва : НИИРПО, 2012 – . – Ежемес. [http://www.e-profobr.ru/].
Интернет-ресурсы:
1. Вся математика в одном месте – математический портал [Электронный
ресурс]. - Режим доступа : http://www.allmath.ru, свободный. - Загл. с
экрана. – (Дата обращения: 03.03.2014).
2. Математика: справочник формул по алгебре и геометрии, решения задач
и примеров. Математические формулы on-line [Электронный ресурс]. -
Режим доступа : http://www.pm298.ru, свободный. - Загл. с экрана. -
(Дата обращения: 03.03.2014).
3. Форум - математический сайт allmatematika.ru [Электронный ресурс]. -
Режим доступа : http://www. allmatematika.ru, свободный. - Загл. с
экрана. - (Дата обращения: 03.03.2014).
4. Электронно-библиотечная система издательства «Лань» [Электронный
ресурс]. - Режим доступа : http://lanbook.com/ebs.php, для доступа к
информ. ресурсам требуется авторизация. - Загл. с экрана.- (Дата
обращения: 03.03.2014).
5. Электронно-библиотечная система «КнигаФонд» [Электронный ресурс]. -
Режим доступа: http://www.knigafund.ru/, для доступа к информ.
ресурсам требуется авторизация. - Загл. с экрана. - (Дата обращения:
03.03.2014).
Скачать материал

Математика - еще материалы к урокам: