Теория графов

У1 У2  У3     Z1 Z2

А = Х1 4 0 2    У1 2  1

Х2 2 3  1    В = У2 0  3

У3 3  0

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

Если нарисовать соответствующую схему, то решить задачу не трудно, попробуем решить матричным методом.

Таким образом, по заданным матрицам А и В требуется определить элементы сi,j матрицы С:

 

Z1 Z2

C = Х1 С11 С12

Х2 С21 С22

 

Рассуждения определяют матрицу С и алгоритм нахождения элементов сi,j, а именно

 

Z1     Z2

C = Х1 (а11в11 + а12в21 + а13в31  а11в12 + а12в22 + а13в32

Х2 (а21в11 + а22в21 + а23в31 а21в12 + а22в22 + а23в32

Z1 Z2

C = Х1 14 4

Х2 7 11

 

Рассмотренная задача убеждает в целесообразности введения еще одной операции над матрицами. Эту операцию принято называть операцией умножения матриц.

Если С = АВ, то элементы матрицы С определяются следующей формулой:

 

сi,j = ai1в1j + ai2в2j + ai3в3j + … + ainвnj

 

Таким образом, элемент сi,j образуется из элементов i-й строки матрицы А и элементов j-го столбца матрицы В.

Следует обратить внимание на следующие два факта:

1) операция умножения  матрицы А на матрицу В определена  только в том случае, если число  столбцов в матрице А равно  числу строк в матрице В.

2) если матрица  А имеет порядок (m x n), а матрица В – порядок (n x r), то матрица – произведение С = АВ имеет порядок (n x m).

Рассмотрим некоторые основные операции, производимые над графами.

Операцией добавления к графу G = <V, U> вершины а образуется граф <V u {a}, U>.

Операцией добавления дуги (а, в) к графу G состоит в образовании графа <V u {a, в), U u {(а, в)}>. При операции удаления дуги, получаем <V, U \ {(а, в)}>. Операции удаления вершины заключается в удалении вершины Vi вместе с инцидентными ей дугами: <V\{Vi}, U \ {(Vj Vk) Vj = Vi или Vk = Vi}>. Операция отождествления вершин (в случае, когда Vi и Vj соединены дугой, операцию называют стягиванием дуги (ViVj).

Пример:

Рис. 11

 

Из графа G, добавлением вершины 5 образуется граф G1, добавлением дуги (3, 1) – G2, удалением дуги (3, 2) – G3, удалением вершины 2 – G4, отождествлением вершин 1 и 4 – G5 , стягиванием дуги (2, 3) – G6.

Добавлением графа без петель G = <V, U> называется граф = <V, V2 \ (U u i av)>.

 

Рис. 12

 

Объединением G1 u G2 называется граф <V1 u V2, U1 u U2>.

Если V1 ∩ V2 ≠ Ø, то пересечением G1 ∩ G2 называется граф <V1 ∩ V2, U1 ∩ U2 >.

Кольцевой суммой G1 + G2, называется граф <V1 u V2, (U1 \ U2) u (U2 \ U2).

Соединением G1 + G2 называется <V1 u V2, U1 u U2 u {[Vi, Vj] | Vi є V2, Vi ≠ Vj}>.

Произведением G1 x G2 называется граф <V1 x V2, U>.

Композицией G1 [G2] называется граф <V1 x V2, U>, в котором ((V1j, V1j), (Vj2, Vj2)) є U, если 1) (Vj1, Vj2) є U1; 2) Vi1 = Vi2, (Vj1, Vj2) є U2.

 

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

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

 

Рис. 14     Рис. 15

 

Пример дерева показан на рис.14, здесь же показаны висячие вершины, на рисунке они выделены закрашенными кружками (вершина дерева, степень которой равна единице, называется висячей вершиной).

Пример леса показан на рис.15.

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

Теорема: дерево с n вершинами имеет n-1 ребро.

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

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

 

Рис. 16

 

Ответ: 8 способами

Рис. 17

 

1.2. Раскраска графов

 

Пусть G = <V, U> - нефграф без петель.

Раскраской (вершин) графа G называется такое задание цветов вершинам G, что если (Vi, Vj)-дуга, то вершины Vi, Vj имеют различные цвета. Хроматическим числом Х (G) графа G называется минимальное число цветов, требующиеся для раскраски G (рис. )

Пример. Так как в полном графе Gn любые две различные вершины связаны ребром, то Х (Gn) = n.

Многие практические задачи сводятся к построению раскрасок графов.

Пример 1. Рассмотрим задачу составления расписания. Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно. Построим граф G, вершины которого биективно соответствуют лекциям и две вершины смежны тогда и только тогда, когда соответствующие им лекции нельзя читать одновременно. Очевидно, что любая раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам одного цвета, могут читаться одновременно. Напротив, любое допустимое расписание определяет раскраску графа G. Оптимальные расписания соответствуют раскраскам с минимальным числом цветов, а число часов, необходимое для прочтения всех лекций, равно Х (G).

Пример 2. Рассмотрим граф G, вершины которого – страны, а ребра соединяют страны, имеющие общую границу. Число Х (G) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны не были окрашены в один цвет.

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

Неорграф G называется бихроматическим, если Х (G) = 2. Неорграф G = <V, U> называется двудольным, если множество всех ребер графа G образует разрез графа G, т.е. для некоторого разбиения множества вершин {V1, V2} концы любого ребра принадлежат разным частям разбиения.

Примером служит задача «Три дома, три колодца».

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

1. Произвольная  вершина V1 графа G принимает цвет 1.

2. Если вершины  V1, …, Vi раскрашены l цветами е, 2, … е, е ≤ i, то новой произвольно взятой вершине Vi+1 припишем минимальный цвет, не использованный при раскраске вершин из множества {Vj | ρ (Vi+1, Vj) = 1, j < i}.

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

Все двудольные графы бихроматические, Х (G) = 2.

Пример:

бихроматический     двудольный

Любой бихроматический граф является двудольным.

Теорема: для того, чтобы граф был бихроматическим, необходимо и достаточно, чтобы он был связным и не содержал элементарных циклов нечетной длины.

Дано: G – бихромат. граф

Док-ть: связный и не содержит циклов нечетной длины

Док-во (от противного)

Пусть граф содержит циклический элемент

Х = 3, но G – бихромат – противоречие.

Обратная теорема:

Дано: G – связный, не содержит циклов нечет. длины

Док-ть: Х (G) = 2

Док-во:

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

2) граф, содержит циклы четной длины

 

 

Глава 2. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ НА ФАКУЛЬТАТИВНЫХ ЗАНЯТИЯХ В ШКОЛЕ

2.1. Роль факультативных  занятий

 

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

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

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

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

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

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

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

Важной вехой в истории советской школы был 1966 г., когда постановление ЦК КПСС и Совета Министров СССР «О мерах дальнейшего улучшения работы средней общеобразовательной школы» рекомендовало всем школам проведение в VII-Х классах факультативных занятий «для углубления знаний учащихся, для развития их интересов, способностей». Впервые все работники просвещения осознали, что такие занятия столь же важны, как и уроки по обязательной программе.

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

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

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

Значение факультативных занятий состоит в том, что они позволяют:

- развивать склонности  и способности учащихся, давая  им соответствующую интеллектуальную  нагрузку;

- удовлетворять  интересы учащихся;

- повышать качество  подготовки учащихся к продолжению  образования;

- развивать творческие  способности учащихся, их самостоятельность;

- знакомить учащихся  с современными достижениями  науки и техники;

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

- способствовать  профессиональной ориентации учащихся.

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

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

2. Курсы прикладной  математики, цель которых – познакомить учащихся с важнейшими путями и методами использования достижений математической науки на практике и развивать их интерес к развитию современной математической науке.

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

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

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