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

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ И НАУКИ КЕМЕРОВСКОЙ ОБЛАСТИ

Государственное образовательное учреждение среднего профессионального образования

Кемеровский профессионально-технический техникум

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

 (статья)

Подготовил преподаватель математики

Валеева Людмила Леонидовна

Кемерово 2015

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

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра^[1]. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

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

Определение 1. Мы го­ворим,  что задан  граф,  если  даны:

1) некоторое конечное множество Х, элементы которого изображены точками; эти элементы могут обо­значать людей, предметы, события, состояния и т. д.;

2) некоторое множество U упо­рядоченных или неупорядоченных пар (а,b), причем аХ, bX; каждая подобная пара соответствует на схе­ме  линии (связи), соединяющей точ­ки а и b (если пара упорядочена, то направление      связи указано стрелкой).^[1]

При этом точки а и b могут иметь и более одной связи. Если для данной пары (а, b) имеется r (r > 1) та­ких связей, то их различают с по­мощью индексов, например, (а, b)₁, (а, b)₂,. . . ,(а, b)_r.

Множества X и U определяют граф G = [X, U]. Граф называется направленным, если элементы мно­жества U являются упорядоченными парами точек (см. рис. 1), и ненаправ­ленным — в противном случае.

Рис. 1.

 

Рис.1

Рис. 3.

Определение 2. Две вер­шины называются связанными, если они соединены ребром. Говорят, что вершина инцидентна ребру, если она служит концом этого ребра.

Определение 3. Если данная вершина инцидентна в G ров­но r ребрам, то r называется связ­ностью данной вершины в G.

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

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

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

Рис. 2.

Определение 4. Граф G называется простым, если он не со­держит дублирующихся ребер, то есть любые две вершины в G связаны не более чем одним ребром (на рисун­ке 2 имеются дублирующие ребра).^[2]

Некоторые теоремы и их применения

Теорема 1. Пусть /Х/ = n – число  вершин, |U| – число  ребер  и s₁, s₂, . . . , s_n – связности вершин графа G = [X, U]. Тогда ,(1) то есть сумма связностей всех вер­шин графа G вдвое больше числа его ребер.

Рис. 5.

 

Рис. 3

Доказательство. Заме­ним каждое ребро двумя половинка­ми (рис. 3). Тогда каждой половинке ребра будет инцидентна одна и толь­ко одна вершина. Если вершина а_iХ имеет связность s_i, то она инцидентна ровно s_i половинкам  ребер; значит, сумма равна числу всех  полуребер или, что то же самое, удвоен­ному числу ребер.

Определение 5. После­довательность ребер, в которой каждое ребро графа G встречается не более одного  раза,   называется цепочкой.

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

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

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

Определение 8. Граф G, в котором каждые две вершины а_i и а_j связаны не менее чем одним путем, называется связным.

Теорема 2. В каждом связ­ном графе G число вершин нечетной связности четно.

Доказательство. Обо­значим сумму связностей «нечетных» вершин (то есть сумму нечетных слагаемых в формуле (1)) через , а сумму связностей «четных» вер­шин (то есть сумму четных слагаемых в (1)) через . Тогда по теореме 1,откуда.                 (2)

Числа 2|U| и , а следовательно, и их разность, стоящая в правой части равенства (2), четны, а потому и левая часть (сумма нечетных слагаемых — ) — число четное. Да­лее легко доказать (от противного), что количество (нечетных!) слагае­мых в этой сумме — четное. Теорема доказана.^[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).