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


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

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ И НАУКИ КЕМЕРОВСКОЙ ОБЛАСТИ
Государственное образовательное учреждение среднего профессионального
образования
Кемеровский профессионально-технический техникум
Элементы графов на примере учебных групп и кабинетов (статья)
Подготовил преподаватель математики
Валеева Людмила Леонидовна
Кемерово 2015
Считается, что задан граф, если даны:
1) некоторое конечное множество Х, элементы которого изображены точками;
эти элементы могут обозначать людей, предметы, события, состояния и т. д.;
2) некоторое множество U упорядоченных или неупорядоченных пар (а,b),
причем а
Х, b
X; каждая подобная пара соответствует на схеме линии (связи),
соединяющей точки а и b (если пара упорядочена, то направление связи
указано стрелкой).
[1]
При этом точки а и b могут иметь и более одной связи. Если для данной
пары (а, b) имеется r (r > 1) таких связей, то их различают с помощью
индексов, например, (а, b)
1
, (а, b)
2
,. . . ,(а, b)
r
.
Множества X и U определяют граф G = [X, U].
Пример: пусть нам даны два множества. Первое множество А – это
множество учебных групп (А
1
, А
2
, А
3
и так далее), а второе В – множество
учебных кабинетов (В
1
, В
2
, В
3
и так далее). Тогда можно изобразить граф, в
котором множества А и В выступают в роли вершин графа. Вершины А
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 была выездная экскурсия (то есть они в этот
день не учатся). Получим следующий граф, в котором группы помещены в
синие овалы, а учебные кабинеты в зеленые прямоугольники:
По изображению графа можно сказать какие и сколько было групп в
данных кабинетах.
Наш граф является направленным, так как элементы множества учебных
групп и кабинетов являются упорядоченными парами. На рисунке это не
изображено, но подразумевается, что ребра направленны от учебных групп в
сторону кабинетов, так как студенты данных групп идут в данные кабинеты, а
не наоборот.
Две вершины называются связанными, если они соединены ребром.
Если данная вершина инцидентна в G ровно r ребрам, то r называется
связностью данной вершины в G.
В данном примере самую большую связность, а именно равную 4, имеют
вершины «М – 01» и «О – 13». А вершина «К – 44» не связанна ни с одной
другой вершиной, следовательно, данная вершина будет изолированной.
Наш граф не является простым, так как он содержит дублирующиеся
ребра, а именно вершины «М – 01» и «407» связанны двумя ребрами, и
вершины «О – 13» и «201» также связанны двумя ребрами.
Иногда в графах бывают вершины, не инцидентные ни одному ребру.
Такие вершины называются изолированными.
Проверим на нашем примере выполнение следующей теоремы:
Рис. 1.
Рис. 3.
М – 01
П – 32
С – 22
О – 13
201
102
205
407
304
С-22
П-32
Теорема. Пусть /Х/ = n – число вершин, |U| – число ребер и s
1
, s
2
, . . . , s
n
– связности вершин графа G = [X, U]. Тогда
n
i
i
Us
1
2
, то есть сумма
связностей всех вершин графа 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).
Скачать материал

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