Элементы графов на примере учебных групп и кабинетов

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

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

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

Элементы графов  на примере учебных групп и кабинетов (статья)

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

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

Кемерово 2015

Считается,  что задан  граф,  если  даны:

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

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

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

Множества X и U определяют граф G = [X, U].

Пример: пусть нам даны два множества. Первое множество А – это множество учебных групп (А₁, А₂, А₃ и так далее), а второе В – множество учебных кабинетов (В₁, В₂, В₃ и так далее). Тогда можно изобразить граф, в котором множества А и В выступают в роли вершин графа. Вершины А_i и В_j соединяются ребром, если в данный день у группы А_i есть занятия в учебном кабинете В_j.

Построим данный граф для учебных групп М – 01, П – 32, С – 22, О – 13, К – 44. Учебные кабинеты: 205, 102, 304, 407, 201. Если известно, что у группы М – 01были занятия в 205, 102 и две пары в 407. У учебной группы П – 32 были пары в 201, 205 и в 304 кабинетах. У учебной группы С – 22 были занятия в 102, 304 и в 407 кабинетах. Учебная группа О – 13 училась в этот день в кабинетах под номером 205 одно занятие, в кабинете 201 – два занятия и в кабинете 304. А у группы К – 44 была выездная экскурсия (то есть они в этот день не учатся). Получим следующий граф, в котором группы помещены в синие овалы, а учебные кабинеты в зеленые прямоугольники:

 

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

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

Рис. 1.

Рис. 3.

Две вер­шины называются связанными, если они соединены ребром.

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

В данном примере самую большую связность, а именно равную 4, имеют вершины «М – 01» и «О – 13». А вершина «К – 44» не связанна ни с одной другой вершиной, следовательно, данная вершина будет изолированной.

Наш граф не является простым, так как он со­держит дублирующиеся ребра, а именно вершины «М – 01» и «407» связанны двумя ребрами, и вершины «О – 13» и «201» также связанны двумя ребрами.

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

Проверим на нашем примере выполнение следующей теоремы:

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

         В нашем случае число  вершин равно 10,  число  ребер  равно 14 и связности вершин следующие: 4, 3, 3, 4, 0, 2, 3, 3, 3, 3.

         Теперь найдем сумму связностей вершин: 4+3+3+4+0+2+3+3+3+3=28.

         Да, действительно сумма связностей всех вершин вдвое больше числа ребер.

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

Начнем с вершины М – 01 из неё пойдем в вершину 102, из которой следует единственный путь в вершину С – 22, далее возможны два варианта 304 и 407, мы проследуем, например, в 304. Из 304 также возможны два варианта О – 13 и П – 32, выберем О – 13. Из данной вершины возможны три варианта: 201, 201 и 205, к примеру выберем 201. Из 201 можно выбрать либо П – 32 или обратно в О – 13, мы выберем П – 32, из которого проследуем в 205. Теперь снова доступны два варианта М – 01 и О – 13, но если мы пойдем в О – 13, то там будет доступен только один ход в 201 и на этом цепочка закончится. В противном случае, если мы пойдем в М – 01, далее идут два ребра, ведущие в 407, из которого возможен обратный ход в М – 01 или в С – 22. И всё цепочка на этом закончилась.

Запишем по порядку последовательность вершин, который составили нашу цепочку: М – 01, 102, С – 22, 304, О – 13, 201, П – 32, 205, М – 01, 407, с – 22.

В нашу цепочку не вошли ребра, связывающие следующие вершины: М – 01 и 407, П – 32 и 304, О – 13 и 201, О – 13 и 205.

Информационное обеспечение

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.             Научные исследования в образовании [Текст] : приложение к журналу «Профессиональное образование. Столица» / учредители Департамент образования города Москвы; Российская академия образования; Академия профессионального образования. – 2006 – . – Москва : НИИРПО, 2012 – . – Ежемес.

2.             Образование. Карьера. Общество [Текст] : учредитель ГОУ «Кузбасский региональный институт развития профессионального образования». – 2005 -.- Кемерово : ГОУ « КРИРПО», 2010 -.- Ежеквар. - [http://www.krirpo.ru/].

3.             Профессиональное образование. Столица [Текст]: информационно-педагогическое, научно-методическое издание / учредители Департамент образования города Москвы; Российская академия образования; Академия профессионального образования. – 1997 – . – Москва : НИИРПО, 2012 – . – Ежемес. [http://www.e-profobr.ru/].

Интернет-ресурсы:

1.             Вся математика в одном месте – математический портал [Электронный ресурс]. - Режим доступа : http://www.allmath.ru, свободный. -  Загл. с экрана. – (Дата обращения: 03.12.2014).

2.             Математика: справочник формул по алгебре и геометрии, решения задач и примеров. Математические формулы on-line [Электронный ресурс]. - Режим доступа : http://www.pm298.ru, свободный. -  Загл. с экрана. - (Дата обращения: 03.12.2014).

3.             Форум - математический сайт allmatematika.ru [Электронный ресурс]. - Режим доступа : http://www. allmatematika.ru, свободный. -  Загл. с экрана. -  (Дата обращения: 03.12.2014).

4.             Электронно-библиотечная система издательства «Лань» [Электронный ресурс]. - Режим доступа : http://lanbook.com/ebs.php, для доступа к информ. ресурсам требуется авторизация. -  Загл. с экрана.-  (Дата обращения: 03.12.2014).

5.             Электронно-библиотечная система «КнигаФонд» [Электронный ресурс]. - Режим доступа: http://www.knigafund.ru/, для доступа к информ. ресурсам требуется авторизация. -  Загл. с экрана.  - (Дата обращения: 03.12.2014).