Особенности элективного курса для старшеклассников «Ориентированные графы и их приложения»
Библиографическое описание статьи для цитирования:
Особенности элективного курса для старшеклассников «Ориентированные графы и их приложения» // Научно-методический электронный журнал «Концепт». –
2014. – Т. 20. – С.
2806–2810. – URL:
http://e-koncept.ru/2014/54825.htm.
Аннотация. Статья посвящена методике проведения элективного курса для старшеклассников «Ориентированные графы и их приложения», приведены примеры содержания занятий.
Текст статьи
Сорокина Анна Андреевна,Учитель математики, МБОУ «Котлубанская СОШ», Волгоградская обл. Городищенский район п. Котлубаньanna_sorokina_84@list.ru
Особенности элективного курса для старшеклассников «Ориентированные графы и их приложения»
Аннотация.Статья посвящена методике проведения элективного курса для старшеклассников «Ориентированные графы и их приложения», приведены примеры содержания занятий.Ключевые слова: алгебра, проблемное обучение, ориентированные графы и их приложения.
Мы живём в период серьёзных изменений в системе образования. Модернизация образования −это не политическая компания, а жизненная необходимость. Стремительное развитие информационного общества, научнотехническийпрогресстребуют от каждого человека высокого уровня профессиональных и деловых качеств, предприимчивости, способности ориентироваться в сложных ситуациях, быстро принимать решения.Однимиз важнейшихнаправлений модернизации образованияявляется профильное обучение. Элективные курсы играют важную роль в системе профильного обучения. Они давнозарекомендовали себя как отличный способ дать ученику дополнительные знания в интересующей его области.В последнее время значительно увеличилась роль математического моделирования как мощного средства научного исследования. Математические модели широко используются при решении производственных задач. Тем не менее, в школьных программах математическоемоделирование рассматривается только в связи с решением текстовых задач.Ориентированные графы являются простым и удобным языком для построения математических моделей различной степени подробности и сложности, эффективным средством для обучения школьников мышлению, связанному с анализом дискретных процессов.Подводя итог вышесказанному, мы сформулировали следующие цели предлагаемого элективного курса «Ориентированные графы и их приложения»:дать первоначальное представление обосновных методах теории графови о возможности их применениядля решения практических задач;способствовать формированию восприятия математики как единого языка познания;способствовать развитиютворческих способностей, целостной картины мираи логического мышления старшеклассников, формированию положительной мотивации к получению знаний.Предлагаемый элективный курсдолжен быть рассчитан, на наш взгляд, на 8 часов.Приведем примернуюпрограммукурса:1.Ориентированый граф и его элементы(1час).2.Полустепень исхода и захода вершины орграфа. Цикл и контур орграфа. Сильносвязный (сильный) орграф.(2часа).3.Связныеорграфы(2 часа).4.Свойства турниров (1 час).5.Гамильтоновы орграфы (2 часа).Занятия должны содержать элементы проблемного обучения, объяснение материала учителем чередоваться с самостоятельным поиском учащимися путей решения поставленных задач. Одной из особенностью предлагаемого курса является то, что изучение материала происходит в основном через систему задач. Возможно встраивание доказательств фактов из теории ориентированных графов в процесс решения задач.Например несколько занятий из курса.Занятие № 1Ориентированый граф и его элементыЗадача № 1Из города А в город В ведут несколько дорог (карту дорог см. на рис 2.1). Найдите число маршрутов автомобильного путешествия из А в В, учитывая, что при движении автомобиль должен все время приближаться к В. Решение.Построим граф G, вкотором вершины соответствуют городам А и В и перекресткам, а ребра —дорогам. Ориентируем ребра, учитывая, что автомобиль все время должен двигаться по направлению от А к В (рис. 2.2).Ориентированный граф G, или орграф, состоит из конечного непустого множества V и множества Е упорядоченных пар элементов из V. Элементы множества Vназываются вершинами орграфа, элементы множества Е —дугами орграфа.Если х = (u, v) —дуга, то вершины uи v называются ее концевыми вершинами, причем uназывается началом дуги, а v
концом дуги. Дуга с совпадающими началом и концом называется петлей. Можно рассматривать орграфы с несколькими дугами, имеющими общие концевые вершины. Такие дуги называются параллельными.Рис. 2.1Рис 2.2На рисунке дуга изображается направленной линией, идущей от начала дуги к концу. Например, если V= {1, 2, 3, 4, 5}, Е = {е1, е2, е3, е4, е5, е6, е7, е8}, где е1=(1, 2), е2=(3,1), е3=(3,1), е4=(3, 2), e5=(2,4), е6=(4,2), е7=(3,4), e8=(4,4), то орграф можно изобразить, как на рис. 2.3. В этом орграфе е2и е3—параллельные дуги, а е8—петля.Вершины орграфа называются смежными, если они являются концевыми вершинами некоторой дуги. В противном случае вершины называются несмежными. Маршрутом L= (е1, e2,..., ер) в орграфе называется такая последовательность его дуг, в которой начало каждой последующей дуги совпадает с концом предыдущей. Маршрут можно также задавать порядком прохождения его вершин. Начало первой дуги маршрута называется его начальной вершиной, а конец последней дуги —конечной вершиной. Маршрут, у которого все дуги разные, называется цепью. Цепь, содержащая каждую свою вершину ровно один раз, называется путем.Для решения задачи необходимо найти в построенном орграфе число различных путей, соединяющих вершины А и В. Для этой цели используем корневое дерево. Из вершины А ведут 3 дуги (рис. 2.4):
Рис 2.3
Рис 2.4 Рис 2.5Попав в вершины 1, 2, 3, мы имеем несколько возможностей для продолжения цепей: из 1 можем попасть в вершины 3,4 и В (в этомслучае мы получили один нужный маршрут); из вершины 2 —в 3 и 5; из вершины 3 —в 4 и 5 (рис. 2.5). Окончательное корневое дерево построения маршрутов будет выглядеть как на рис. 2.6. Из городаА в город В ведет 9 маршрутов.Рис 2.6Задача №2На острове отдельными селениями живут правдолюбы ишутники. Правдолюбы постоянно говорят правду, а шутники всегда лгут. Жители каждого племени могут бывать в селении другого племени. Докажите, что путешественнику, попавшему в селение, достаточно задать первому встречному вопрос: «Вы местный?», чтобы по ответу определить, в селении какого племени он находится.Решение.У путешественника 4 возможности: он может оказаться водном из двух селений, где ему может попасться или правдолюб, или шутник. Корневое дерево ниже описывает эти возможности и ответы, полученные в каждом из случаев.Рис 2.7Из рисунка 2.7 видно, что в случае ответа «да» путешественник находится в селении правдолюбов, в случае ответа «нет» —в селении шутников. Задача № 3В стране 101 город. Города соединены дорогами с односторонним движением так, что два города соединены не более чем одной дорогой. Из любого города выходит ровно 50 дорог, и в любой город входит ровно 50 дорог. Докажите, что из любого города в любой другой можно попасть, проехав не более двух дорог.Решение.Зададим схему дорог в стране ориентированным графом. Рассмотрим две произвольные такие вершины uи v, что в орграфе нет дуги (u, v).Длиной маршрута называется число дуг, входящих в маршрут. Расстоянием d(u,v) между вершинами uи v называется наименьшая длина маршрута, начальной вершиной которого является вершина u, а конечной —вершина v. Очевидно, чтотакой маршрут будет цепью.Для решения задачи нужно доказать, что расстояние между двумя любыми вершинами орграфа не более двух. Пусть из вершины uвыходят дуги (u, u1), (u, u2),..., (u, u50), а в вершину v входят дуги (v1,v), (v2, v),..., (v50, v). Среди вершин uiи vjдолжна существовать общая вершина w, так как в противном случае в орграфе окажется не менее 102 вершин.Маршрут (u, w, v) в орграфе определяет нужный маршрут проезда городов.Домашняя работаЗадача № 4В стране 101 город. Города соединены дорогами с односторонним движением так, что два города соединены не более чем одной дорогой. Из любого города выходит ровно 40 дорог, и в любой город входит ровно 40 дорог. Докажите, что из любого города в любой другой можно попасть, проехав не более трех дорог.Решение.Зададим схему дорог в стране ориентированным графом. Нужно доказать, что расстояние между любыми двумя вершинами орграфа не более трех. Рассмотрим две произвольные такие вершины uи v, что в орграфе нет дуги (u, v) и нет дуг (u, w) и (w, v).Пусть из вершины uвыходят дуги (u, u1), (u, u2),..., (u, u40), а в вершину v входятдуги (v1, v), (v2, v),..., (v40, v). Вследствие выбора вершин uи v среди вершин uiи vjнет совпадающих.Из вершин множества U = {u1, u2,..., u40} выходят 1600 дуг. В то же время число дуг между вершинами самого множества U не превосходит 40*39/2 =780, ачисло дуг из U в 19 вершин, не принадлежащих множеству {u, u1,..., u40, v, v1, …, v40}, не больше, чем 40•19 = 760. Так как 1600>780+760, то должна существовать дуга, выходящая из некоторой вершины uiи входящая в некоторую вершину vj.Путь L=(u, ui, vj, v) содержит три дуги. Этот путь определяет нужный путь между городами.Занятие № 2Полустепень исхода d+(v). Полустепень захода d(v). Цикл и контур орграфа. Сильносвязный (сильный) орграф.Задача № 5В стране есть столица и еще 100 городов. Некоторые города(в том числе и столица) соединены дорогами с односторонним движением. Из каждого города, кроме столичного, выходит 20 дорог и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.Решение.
Рассмотрим орграфG, в котором вершины будут обозначать города, а дуги —дороги с установленным направлением движения по ним. Полустепенью исхода d+(v) вершины v называется число дуг, выходящих из вершины v. Полустепенью захода d(v) вершины v называется число дуг, входящих в вершину v. Поскольку каждая дуга выходит из одной вершины и входит одну, то очевидно следующее утверждение:Сумма полустепеней захода вершин орграфа равна сумме их полустепеней исхода и равна числу дуг орграфа.В графе G для всех вершин, кроме столицы,d+(v) = 20, d(v) = 21. Пусть вершина uорграфа,соответствующая столице, имеетполустепень захода d(u)=х и полустепень исхода d+(u)=у. Из условия задачи ледует, что х + у≤100, или у≤ 100 х.Воспользуемсяприведенным выше утверждением:21•100+х =20•100+у≤20•100+(100х). Отсюда 2х≤0, и х=0. Так как полустепень захода вершины uравно нулю, то в вершину uне входит ни одна дуга, и в столицу невозможно въехать ни по одной дороге.Задача №6В школе учатся 1000 учеников. Каждому из них нравятся ровно к учеников из остальных. При каких значениях к можно утверждать, что обязательно найдутся два ученика школы, которые или оба нравятся, или оба не нравятся друг другу? Решение.Рассмотрим орграф G, имеющий 1000 вершин, соответствующий ученикам. Вершины uи v будут соединены дугой (u, v) тогда и только тогда, когда ученику, соответствующему вершине u, нравится ученик, соответствующий вершине v. По условию задачи полустепень исхода каждой вершины орграфа равна k. Необходимо определить, при каком kв орграфе G обязательно найдутся две такие вершины uи v, которые или соединены двумя дугами (u, v) и (v, u), или не соединены ни одной дугой.Предположим, что при некотором kкаждую пару вершин соединяет ровно одна дуга. Тогда число дуг в орграфе будет равно числу пар учеников, т. е. (1000•999)/2= =500•999. С другой стороны, из каждой вершины орграфа выходит ровно kдуг, т. е. всего 1000•kдуг. Приравняем эти числа. 500999=1000•k. Отсюда 2k=999. Последнее равенство невозможно ни при каком k. Поэтому при любом к в школе обязательно найдутся два ученика, которые или оба нравятся друг другу, или оба не нравятся друг другу.Задача №8В волейбольном турнире проведено несколько матчей, после чего у каждой команды оказалась хотя бы одна победа. Докажите, что из сыгранных матчей можно выбрать несколько так, что если учитывать только эти матчи, то у каждой команды, принимающей участие в них, будет ровно одна победа и одно поражение.Решение.Опишем проходящее соревнование ориентированным графом. В этом графе вершина viобозначает команду viи дуга (vi,vj) существует тогда и только тогда, когда команда viвыиграла у команды vj. Цепь называется циклом, если ее начальная и конечная вершины совпадают. Цикл орграфа, все вершины которого различные, называется контуром. Для решения задачи нужно доказать, что в построенном орграфе существует контур. Выберем любую вершину v1орграфа. Поскольку из нее выходит хотя бы одна дуга, перейдем по этой дуге в соседнюю вершину v2. Аналогично из v2 перейдем в v3 ит.д. Поскольку число вершин в орграфе конечно, то в конце концов мы попадем в вершину, в которой были ранее (см. рис 2.8).Рис. 2.8Полученный контур определяет необходимые встречи команд.Задача № 9В одном из городов Трансильвании 2006 жителей. Из них трое являются вампирами, а остальные нет. Писатель Стокер попросил каждого жителя указать двух человек, которые, по его мнению, являются вампирами. Известно, что вампиры обязательно укажут вампиров, а обычные жители могут указать на кого угодно. Докажите, что, пользуясь эти данными, Стокер может выбрать себе двух спутников для путешествия, которые не будут вампирами.Решение.Рассмотрим орграф, вершины которого соответствуют жителям города, и две вершины будут соединены дугой, если один житель укажет на другого. Поскольку среди жителей есть три вампира, то в орграфе обязательносуществует подграф Т как на рис. 2.9 (подграф ориентированногографа определяется аналогично подграфу графа). Однако подобные подграфы могут порождать и жители, не являющиеся вампирами. Будем называть такие подграфы «подозрительными». Вампиры могут находиться лишь среди людей, соответствующих «подозрительным» подграфам. Найдем «подозрительный» подграф и удалим его из графа. Если в получившемся графе нет больше «подозрительных» подграфов, то все люди, оответствующие оставшимся вершинам —не вампиры. Если же такие подграфы есть, то будем поочередно удалять их из графа. Поскольку при делении числа 2006 на 3 получается остаток 2, то можно утверждать, что мы, таким образом, определим хотя бы двух человек, заведомо не являющихся вампирами.Рис. 2.9Задача № 10В одном приморском курортном городе улицы настолько узкие,что в городе установлено одностороннее транспортное движение. Тем не менее, из каждой точки города можно проехать в любую другую. Докажите, что можно предложить такой маршрут патрулирования для полицейской машины, который начинается и оканчивается в одном и том же месте и проходит через каждый участок улиц между двумя перекрестками по крайней мере один раз.Решение.Рассмотрим ориентированный граф G, задающий движение по улицам города.Вершина орграфа v называется достижимой из вершины u, если существует маршрут, в котором вершина uявляется начальной, а вершина v —конечной. Орграф называется сильносвязным (сильным), если для любых вершин uи v, вершина uдостижима из вершины v, а вершина v достижима из вершины u. Из условия следует, что орграф G —сильный. Необходимо построить маршрут, который начинается и оканчивается в одной и той же вершине uсодержит все дуги орграфа.Рассмотрим две произвольные вершины u1и v1. В орграфе существует маршрут, соединяющий вершины u1и v1, и маршрут,соединяющий вершины v1и u1. Объединим эти маршруты в один маршрут L1. Он будет начинаться и оканчиваться в вершине u1. Если этот маршрут будет содержать все дуги орграфа, то он будет искомым.Рис. 2.10Предположим, что в орграфе остались дуги, не вошедшие в маршрут L1. Рассмотрим дугу (u2, v1), причем u2принадлежит L1, av2 не принадлежит L1. В орграфе существует маршрут, соединяющий вершины v2 и u2. Вместе с дугой (u2, v2) он будетобразовывать маршрут L2 ,который начинается и оканчивается в вершине v2. Объединим маршруты L1и L2в один маршрут L(см. рис. 2.10). (Возможно, что маршруты имеют общие ребра.)Если маршрут Lне содержит все дуги орграфа G, то увеличим его с помощью некоторого маршрута L3, и так до тех пор, пока не получим нужный маршрут. Этот маршрут и будет соответствовать маршруту патрулирования.Домашняя работаЗадача № 11В одном государстве некоторые города соединены дорогами с односторонним движением. Оказалось, что при появлении любой новой дороги с односторонним движением между городами, которые до зтого не были соединены дорогами, стало возможным добраться из любого города в любой другой, не нарушая правил. Докажите, что такая возможность была и до появления новой дороги.Решение.Города и дороги государства задают ориентированный граф G. Новый орграф, получившийся из Gдобавлением дуги между любыми несмежными вершинами, является сильносвязным. Необходимо доказать, что орграф Gтакже сильносвязный. Пусть в орграфе Gсуществуют вершины uи v, не соединенные путем. Из условия задачи следует, что после добавления дуги (w1,w2), которой не было в орграфе G, в получившемся орграфепоявляется путь L1= (u,..., w1,w2, а, Ь,..., v) из вершины uв вершину v. Но путь L2= (u, с, d,..., w2, w1,..., v) из uв vпоявляется и при добавлении дуги (w2, w1). Тогда путь L= (u, с, d,..., w2, a, b,..., v) соединяет вершины uи vв орграфе G, что противоречит начальному предположению.Следовательно, в орграфе G любая вершина v достижима из любой вершины u, и орграф G сильносвязный. Задача №7B классе 30 человек. Каждому нравятся ровно kучеников1 из класса. При каком минимальном kможно утверждать, что обязательно найдутся два человека, которые нравятся друг другу?Решение.Как в предыдущей задаче, опишем симпатии школьников ориентированным графом. Если полустепень исхода к каждой вершины равна 15, то орграф содержит 30•15=450 дуг. В то же время в орграфе 30• 29/2 = 435 пар вершин. Поэтому хотя бы одна пара должна быть соединена двумя противоположно направленными дугами. Школьники, соответствующие этим вершинам, испытывают взаимные симпатии. Покажем, что k=15 является минимальновозможным числом. Пример для k15 строится так: расположим все вершины по кругу, после чего будем считать, что дуги идут из вершины ровно в kвершин, следующих за ней по часовой стрелке. Занятие № 3Односторонний орграф. Конденсация орграфа.Задача № 13B стране несколько городов. Между некоторыми из них в одном направлении летают самолеты. Известно, что для двух любых городов А и В можно (используя, если нужно, рейсы между другими городами) или долететь из А в В, или долететь из В в А. Докажите, что Рис. 2.11в этой стране можно, вылетев из некоторого города, побывать во всех остальных. Решение.Построим орграф авиалиний, в котором вершины будут обозначать города,а дуги —авиалинии между ними.Орграф называется односторонним, если для любых вершин по крайней мере одна достижима из другой. По условию задачи построенныйорграф является односторонним.Теорема: Граф является односторонним тогда и только тогда, когда в нем есть маршрут, содержащий все вершины орграфа.Доказательство. Необходимость.Рассмотрим маршрут в орграфе L=(v1, v2,..., vk), содержащий наибольшее число вершин. Так как для любых трех вершин орграфа хотя бы из одной достижимы две другие, то k≥3. Если маршрут содержит все вершины орграфа, то теорема верна.Пусть существует вершина u, не входящая в L. Если вершина v1 достижима из вершины u, то в орграфе существует маршрут, содержащий больше вершин,чем маршрут L, что противоречит выбору L(см. рис. 2.11). То же произойдет, если вершина uдостижима из вершины vk. Предположим, что это не выполняется.Рассмотрим две соседние в маршруте Lвершины х и у. Если из одной из них (например, вершины х) достижима вершина u, а вторая достижима из u, то в орграфе есть маршрут L1=(v1,...,x,...,u,...,y,...,vk), содержащее большее число вершин, чем L(см. рис. 2.12).Пусть это не выполняется. Тогда в орграфе снова существует маршрут L2=(v1,..., u,..., v2,..., vk) или L3=(v1..., vk1,...,u,...,vk) с большим числом вершин, чем L(см. рис. 2.13). Достаточность очевидна.Теорема доказана.Из теоремы следует существование в стране нужного маршрута облета городов.Рис. 2.12Рис. 2.13Задача № 14В королевстве 30 городов,некоторые из них соединены дорогами, так что из любого города можно доехать в любой другой. Из каждого города выходит не менее двух дорог, и между двумя городами не более одной дороги. Для того чтобы добиться большей безопасности, король Людовик установилна дорогах одностороннее движение так, чтобы в каждый город входила и выходила хотя бы одна дорога. Тем не менее, некоторые города стали недостижимы для проезда из других. Однако король никогда не признаетсвоих ошибок. Чтобы исправить создавшееся положение, он приказал построить новые дороги с односторонним движением. Докажите, что достаточно построить не более 10 дорог.Решение.Города королевства, его дороги с установленным односторонним движением задают ориентированный граф G. Необходимо доказать, что к графу G можно так добавить не более 10 дуг, чтобы превратить его в сильный орграф.Сильносвязной компонентой называется максимальный по включению подграф орграфа, который является сильным. (Максимальный по включению подграф —это такой подграф, который не содержится в подграфе с теми же свойствами, но с большим числом вершин или ребер.)Пусть G1,G2,...,Gk—сильносвязные компоненты орграфа G. Конденсацией орграфа G называется орграф G*, вершины которого u1, u2,..., ukсоответствуют сильным компонентам орграфа G, и вершина u1соединена дугой с вершиной ujтогда и только тогда, когда в орграфе G есть дуга, выходящая из компоненты Gi, и заходящая в компоненту Gj.На рис. 2.14 изображен орграф G и его конденсация —орграф G*. Орграф G имеет 6 сильносвязных компонент: орграфы G1, порожденный вершинами (v1,v2,v3), G2
вершинами (v4, v5, v6), G3—вершинами (v7, v8, v9,v10), G4—вершинами (v11, v12, v13, v14), G6—вершинами (v16, v17), сильносвязная компонента G5состоит из вершины v15.Конденсацией сильносвязного орграфа является граф К1.Теорема. Конденсация любого орграфа не имеет контуров.Доказательство:Пусть G= (u0,..., ui,..., uj,..., u0) —контур в орграфе G*. Тогда для любой вершины vi
Gi
существует маршрут в любую вершина vj Gj, а из vjмаршрут в vi. Но это противоречит максимальности сильносвязных компонент. Теорема доказана.Рис. 2.14Сильносвязная компонента будет называться концевой, если в конденсации ей будет соответствовать или вершина с нулевой полустепенью исхода, или с нулевой полустепенью захода. Для графа G, соответствующего городам и дорогам с односторонним движением королевства, рассмотрим концевые компоненты. Поскольку для любой ее вершины в нее входит и выходит ровно одна дуга, и две вершины не могут соединятьдве дуги, то каждая концевая компонента состоит не менее, чем из трех вершин. Поэтому в орграфе неболее 10 концевых компонент. Занумеруем концевые компоненты и соединим некоторую вершину первой из них с некоторой вершиной второй, некоторую вершину второй с некоторой вершинойтретьей и т.д., некоторую вершину последней из них с некоторой вершиной первой. Добавив, таким образом, не более 10 дуг, получим сильный орграф. Добавленные дуги соответствуют дорогам, которые нужно построить.Задача № 15Король Людовик приказал так установить одностороннее движение на дорогах между городами своего королевства, чтобы из каждого города в любой другой можно было проехать не более чем по двум дорогам. Оказалось, что после закрытия любой дороги на ремонт из каждого города попрежнему можно проехать в любой другой. Докажите, что теперь для этого нужно не более трех дорог.Решение.Города королевства, его дороги с установленным односторонним движением задают сильный орграф G, в котором расстояние между любыми двумя вершинами не более двух. Рассмотрим орграф G1, который получается из графа G после удаления дуги (u,v). Поскольку по условию задачи орграф G1сильный, то из вершины uдолжна выходить хотя бы одна дуга (u,u0). Но в графе G, а значит uв G1, существует цепь (u0,w,v). Поэтому вершины uи vсоединяет цепь (u,u0,w,v), состоящая из трех дуг. Аналогично рассматривается случай, когда удаление дуги (u,v) разрушает некоторую цепь, состоящую из двух дуг. Дуги построенных цепей соответствуют нужным дорогам в королевстве.Задача № 16В королевстве более четырех городов. Король Людовик приказал так соединить каждые два города авиалиниями, по которым самолеты летают в одном направлении, чтобы из любого города в любой другой можно было перелететь с помощью не более двух авиарейсов. Докажите, что это можно сделать.Рис. 2.15Решение.Для решения задачи необходимо ориентировать ребра графа Кn(n�4), чтобы расстояние между двумя любыми вершинами получившегося орграфа оказалось не более двух. Требуемая ориентация ребер графов K3и К6 представлена на рис. 2.15.Схема перехода от ориентации Тn
графа Кn
к ориентации графа Кn+2указана на рис. 2.16. Для этой цели к орграфу Тnс вершинами v1, v2, ..., vnдобавим вершины vn+1 и vn+2и дуги (vn+1,v1), (vn+1,v2), ...,(vn+1,vn), (v1,vn+2), (v2,vn+2), …,(v3,vn+2),и (vn+2,vn+1). При n=4 требуемая ориентация невозможна. Построенная ориентация вершин графа определит направления авиарейсов между городами. Рис. 2.16
Ссылки на источники1.Мельников О.И., Занимательные задачи по теории графов. Минск: ТетраСистемс, 2001. С. 144.2.Березина Л.Ю., Графы и их применение. М.: Просвещение, 1979. С. 143.3.Уилсон Р., Введение в теорию графов. М.: Мир, 1977. С. 207.4.Конное В.В., Клековкин Г.А., Коннова Л.Я., Геометрическая теория графов. М.: Народное образование, 1999. С. 240.5. Коннова Л.Я., Знакомьтесь, графы. Самара: Издво Института повышения квалификации работников образования, 2001. С. 108.6. Горбачев Я.В., Сборник олимпиадных задач по математике. М.: Издво МЦНМО, 2004. С. 560.7. Мельников О.Я.,Современные аспекты обучения дискретной математике. Глава 7. Минск: БГУ, 2002. С. 120.8. Мельников О.Я., Куприянович В.В.,Использование графовых задач при самостоятельной работе для развития воображения школьников //Народная асвета. 2002. № 10. С. 3133.9. Мельников О.И.,Графы в обучении математики //Математика в школе. 2003. № 8. С. 6772.
Sorokina Anna Andreevnathe teacher of Maths, MBEI «Kotluban secondary school», Volgograd region Gorodischensky district s. Kotlubananna_sorokina_84@list.ruFeatures of teaching elective courses for seniors pupils «The oriented graphs and their applications»Abstract.The article is devoted to the methods of teaching the ellective course for seniors pupils “The oriented graphs and their applications” with applications.Key words: algebra, problem teaching, oriented graphs and their applications/
Особенности элективного курса для старшеклассников «Ориентированные графы и их приложения»
Аннотация.Статья посвящена методике проведения элективного курса для старшеклассников «Ориентированные графы и их приложения», приведены примеры содержания занятий.Ключевые слова: алгебра, проблемное обучение, ориентированные графы и их приложения.
Мы живём в период серьёзных изменений в системе образования. Модернизация образования −это не политическая компания, а жизненная необходимость. Стремительное развитие информационного общества, научнотехническийпрогресстребуют от каждого человека высокого уровня профессиональных и деловых качеств, предприимчивости, способности ориентироваться в сложных ситуациях, быстро принимать решения.Однимиз важнейшихнаправлений модернизации образованияявляется профильное обучение. Элективные курсы играют важную роль в системе профильного обучения. Они давнозарекомендовали себя как отличный способ дать ученику дополнительные знания в интересующей его области.В последнее время значительно увеличилась роль математического моделирования как мощного средства научного исследования. Математические модели широко используются при решении производственных задач. Тем не менее, в школьных программах математическоемоделирование рассматривается только в связи с решением текстовых задач.Ориентированные графы являются простым и удобным языком для построения математических моделей различной степени подробности и сложности, эффективным средством для обучения школьников мышлению, связанному с анализом дискретных процессов.Подводя итог вышесказанному, мы сформулировали следующие цели предлагаемого элективного курса «Ориентированные графы и их приложения»:дать первоначальное представление обосновных методах теории графови о возможности их применениядля решения практических задач;способствовать формированию восприятия математики как единого языка познания;способствовать развитиютворческих способностей, целостной картины мираи логического мышления старшеклассников, формированию положительной мотивации к получению знаний.Предлагаемый элективный курсдолжен быть рассчитан, на наш взгляд, на 8 часов.Приведем примернуюпрограммукурса:1.Ориентированый граф и его элементы(1час).2.Полустепень исхода и захода вершины орграфа. Цикл и контур орграфа. Сильносвязный (сильный) орграф.(2часа).3.Связныеорграфы(2 часа).4.Свойства турниров (1 час).5.Гамильтоновы орграфы (2 часа).Занятия должны содержать элементы проблемного обучения, объяснение материала учителем чередоваться с самостоятельным поиском учащимися путей решения поставленных задач. Одной из особенностью предлагаемого курса является то, что изучение материала происходит в основном через систему задач. Возможно встраивание доказательств фактов из теории ориентированных графов в процесс решения задач.Например несколько занятий из курса.Занятие № 1Ориентированый граф и его элементыЗадача № 1Из города А в город В ведут несколько дорог (карту дорог см. на рис 2.1). Найдите число маршрутов автомобильного путешествия из А в В, учитывая, что при движении автомобиль должен все время приближаться к В. Решение.Построим граф G, вкотором вершины соответствуют городам А и В и перекресткам, а ребра —дорогам. Ориентируем ребра, учитывая, что автомобиль все время должен двигаться по направлению от А к В (рис. 2.2).Ориентированный граф G, или орграф, состоит из конечного непустого множества V и множества Е упорядоченных пар элементов из V. Элементы множества Vназываются вершинами орграфа, элементы множества Е —дугами орграфа.Если х = (u, v) —дуга, то вершины uи v называются ее концевыми вершинами, причем uназывается началом дуги, а v
концом дуги. Дуга с совпадающими началом и концом называется петлей. Можно рассматривать орграфы с несколькими дугами, имеющими общие концевые вершины. Такие дуги называются параллельными.Рис. 2.1Рис 2.2На рисунке дуга изображается направленной линией, идущей от начала дуги к концу. Например, если V= {1, 2, 3, 4, 5}, Е = {е1, е2, е3, е4, е5, е6, е7, е8}, где е1=(1, 2), е2=(3,1), е3=(3,1), е4=(3, 2), e5=(2,4), е6=(4,2), е7=(3,4), e8=(4,4), то орграф можно изобразить, как на рис. 2.3. В этом орграфе е2и е3—параллельные дуги, а е8—петля.Вершины орграфа называются смежными, если они являются концевыми вершинами некоторой дуги. В противном случае вершины называются несмежными. Маршрутом L= (е1, e2,..., ер) в орграфе называется такая последовательность его дуг, в которой начало каждой последующей дуги совпадает с концом предыдущей. Маршрут можно также задавать порядком прохождения его вершин. Начало первой дуги маршрута называется его начальной вершиной, а конец последней дуги —конечной вершиной. Маршрут, у которого все дуги разные, называется цепью. Цепь, содержащая каждую свою вершину ровно один раз, называется путем.Для решения задачи необходимо найти в построенном орграфе число различных путей, соединяющих вершины А и В. Для этой цели используем корневое дерево. Из вершины А ведут 3 дуги (рис. 2.4):
Рис 2.3
Рис 2.4 Рис 2.5Попав в вершины 1, 2, 3, мы имеем несколько возможностей для продолжения цепей: из 1 можем попасть в вершины 3,4 и В (в этомслучае мы получили один нужный маршрут); из вершины 2 —в 3 и 5; из вершины 3 —в 4 и 5 (рис. 2.5). Окончательное корневое дерево построения маршрутов будет выглядеть как на рис. 2.6. Из городаА в город В ведет 9 маршрутов.Рис 2.6Задача №2На острове отдельными селениями живут правдолюбы ишутники. Правдолюбы постоянно говорят правду, а шутники всегда лгут. Жители каждого племени могут бывать в селении другого племени. Докажите, что путешественнику, попавшему в селение, достаточно задать первому встречному вопрос: «Вы местный?», чтобы по ответу определить, в селении какого племени он находится.Решение.У путешественника 4 возможности: он может оказаться водном из двух селений, где ему может попасться или правдолюб, или шутник. Корневое дерево ниже описывает эти возможности и ответы, полученные в каждом из случаев.Рис 2.7Из рисунка 2.7 видно, что в случае ответа «да» путешественник находится в селении правдолюбов, в случае ответа «нет» —в селении шутников. Задача № 3В стране 101 город. Города соединены дорогами с односторонним движением так, что два города соединены не более чем одной дорогой. Из любого города выходит ровно 50 дорог, и в любой город входит ровно 50 дорог. Докажите, что из любого города в любой другой можно попасть, проехав не более двух дорог.Решение.Зададим схему дорог в стране ориентированным графом. Рассмотрим две произвольные такие вершины uи v, что в орграфе нет дуги (u, v).Длиной маршрута называется число дуг, входящих в маршрут. Расстоянием d(u,v) между вершинами uи v называется наименьшая длина маршрута, начальной вершиной которого является вершина u, а конечной —вершина v. Очевидно, чтотакой маршрут будет цепью.Для решения задачи нужно доказать, что расстояние между двумя любыми вершинами орграфа не более двух. Пусть из вершины uвыходят дуги (u, u1), (u, u2),..., (u, u50), а в вершину v входят дуги (v1,v), (v2, v),..., (v50, v). Среди вершин uiи vjдолжна существовать общая вершина w, так как в противном случае в орграфе окажется не менее 102 вершин.Маршрут (u, w, v) в орграфе определяет нужный маршрут проезда городов.Домашняя работаЗадача № 4В стране 101 город. Города соединены дорогами с односторонним движением так, что два города соединены не более чем одной дорогой. Из любого города выходит ровно 40 дорог, и в любой город входит ровно 40 дорог. Докажите, что из любого города в любой другой можно попасть, проехав не более трех дорог.Решение.Зададим схему дорог в стране ориентированным графом. Нужно доказать, что расстояние между любыми двумя вершинами орграфа не более трех. Рассмотрим две произвольные такие вершины uи v, что в орграфе нет дуги (u, v) и нет дуг (u, w) и (w, v).Пусть из вершины uвыходят дуги (u, u1), (u, u2),..., (u, u40), а в вершину v входятдуги (v1, v), (v2, v),..., (v40, v). Вследствие выбора вершин uи v среди вершин uiи vjнет совпадающих.Из вершин множества U = {u1, u2,..., u40} выходят 1600 дуг. В то же время число дуг между вершинами самого множества U не превосходит 40*39/2 =780, ачисло дуг из U в 19 вершин, не принадлежащих множеству {u, u1,..., u40, v, v1, …, v40}, не больше, чем 40•19 = 760. Так как 1600>780+760, то должна существовать дуга, выходящая из некоторой вершины uiи входящая в некоторую вершину vj.Путь L=(u, ui, vj, v) содержит три дуги. Этот путь определяет нужный путь между городами.Занятие № 2Полустепень исхода d+(v). Полустепень захода d(v). Цикл и контур орграфа. Сильносвязный (сильный) орграф.Задача № 5В стране есть столица и еще 100 городов. Некоторые города(в том числе и столица) соединены дорогами с односторонним движением. Из каждого города, кроме столичного, выходит 20 дорог и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.Решение.
Рассмотрим орграфG, в котором вершины будут обозначать города, а дуги —дороги с установленным направлением движения по ним. Полустепенью исхода d+(v) вершины v называется число дуг, выходящих из вершины v. Полустепенью захода d(v) вершины v называется число дуг, входящих в вершину v. Поскольку каждая дуга выходит из одной вершины и входит одну, то очевидно следующее утверждение:Сумма полустепеней захода вершин орграфа равна сумме их полустепеней исхода и равна числу дуг орграфа.В графе G для всех вершин, кроме столицы,d+(v) = 20, d(v) = 21. Пусть вершина uорграфа,соответствующая столице, имеетполустепень захода d(u)=х и полустепень исхода d+(u)=у. Из условия задачи ледует, что х + у≤100, или у≤ 100 х.Воспользуемсяприведенным выше утверждением:21•100+х =20•100+у≤20•100+(100х). Отсюда 2х≤0, и х=0. Так как полустепень захода вершины uравно нулю, то в вершину uне входит ни одна дуга, и в столицу невозможно въехать ни по одной дороге.Задача №6В школе учатся 1000 учеников. Каждому из них нравятся ровно к учеников из остальных. При каких значениях к можно утверждать, что обязательно найдутся два ученика школы, которые или оба нравятся, или оба не нравятся друг другу? Решение.Рассмотрим орграф G, имеющий 1000 вершин, соответствующий ученикам. Вершины uи v будут соединены дугой (u, v) тогда и только тогда, когда ученику, соответствующему вершине u, нравится ученик, соответствующий вершине v. По условию задачи полустепень исхода каждой вершины орграфа равна k. Необходимо определить, при каком kв орграфе G обязательно найдутся две такие вершины uи v, которые или соединены двумя дугами (u, v) и (v, u), или не соединены ни одной дугой.Предположим, что при некотором kкаждую пару вершин соединяет ровно одна дуга. Тогда число дуг в орграфе будет равно числу пар учеников, т. е. (1000•999)/2= =500•999. С другой стороны, из каждой вершины орграфа выходит ровно kдуг, т. е. всего 1000•kдуг. Приравняем эти числа. 500999=1000•k. Отсюда 2k=999. Последнее равенство невозможно ни при каком k. Поэтому при любом к в школе обязательно найдутся два ученика, которые или оба нравятся друг другу, или оба не нравятся друг другу.Задача №8В волейбольном турнире проведено несколько матчей, после чего у каждой команды оказалась хотя бы одна победа. Докажите, что из сыгранных матчей можно выбрать несколько так, что если учитывать только эти матчи, то у каждой команды, принимающей участие в них, будет ровно одна победа и одно поражение.Решение.Опишем проходящее соревнование ориентированным графом. В этом графе вершина viобозначает команду viи дуга (vi,vj) существует тогда и только тогда, когда команда viвыиграла у команды vj. Цепь называется циклом, если ее начальная и конечная вершины совпадают. Цикл орграфа, все вершины которого различные, называется контуром. Для решения задачи нужно доказать, что в построенном орграфе существует контур. Выберем любую вершину v1орграфа. Поскольку из нее выходит хотя бы одна дуга, перейдем по этой дуге в соседнюю вершину v2. Аналогично из v2 перейдем в v3 ит.д. Поскольку число вершин в орграфе конечно, то в конце концов мы попадем в вершину, в которой были ранее (см. рис 2.8).Рис. 2.8Полученный контур определяет необходимые встречи команд.Задача № 9В одном из городов Трансильвании 2006 жителей. Из них трое являются вампирами, а остальные нет. Писатель Стокер попросил каждого жителя указать двух человек, которые, по его мнению, являются вампирами. Известно, что вампиры обязательно укажут вампиров, а обычные жители могут указать на кого угодно. Докажите, что, пользуясь эти данными, Стокер может выбрать себе двух спутников для путешествия, которые не будут вампирами.Решение.Рассмотрим орграф, вершины которого соответствуют жителям города, и две вершины будут соединены дугой, если один житель укажет на другого. Поскольку среди жителей есть три вампира, то в орграфе обязательносуществует подграф Т как на рис. 2.9 (подграф ориентированногографа определяется аналогично подграфу графа). Однако подобные подграфы могут порождать и жители, не являющиеся вампирами. Будем называть такие подграфы «подозрительными». Вампиры могут находиться лишь среди людей, соответствующих «подозрительным» подграфам. Найдем «подозрительный» подграф и удалим его из графа. Если в получившемся графе нет больше «подозрительных» подграфов, то все люди, оответствующие оставшимся вершинам —не вампиры. Если же такие подграфы есть, то будем поочередно удалять их из графа. Поскольку при делении числа 2006 на 3 получается остаток 2, то можно утверждать, что мы, таким образом, определим хотя бы двух человек, заведомо не являющихся вампирами.Рис. 2.9Задача № 10В одном приморском курортном городе улицы настолько узкие,что в городе установлено одностороннее транспортное движение. Тем не менее, из каждой точки города можно проехать в любую другую. Докажите, что можно предложить такой маршрут патрулирования для полицейской машины, который начинается и оканчивается в одном и том же месте и проходит через каждый участок улиц между двумя перекрестками по крайней мере один раз.Решение.Рассмотрим ориентированный граф G, задающий движение по улицам города.Вершина орграфа v называется достижимой из вершины u, если существует маршрут, в котором вершина uявляется начальной, а вершина v —конечной. Орграф называется сильносвязным (сильным), если для любых вершин uи v, вершина uдостижима из вершины v, а вершина v достижима из вершины u. Из условия следует, что орграф G —сильный. Необходимо построить маршрут, который начинается и оканчивается в одной и той же вершине uсодержит все дуги орграфа.Рассмотрим две произвольные вершины u1и v1. В орграфе существует маршрут, соединяющий вершины u1и v1, и маршрут,соединяющий вершины v1и u1. Объединим эти маршруты в один маршрут L1. Он будет начинаться и оканчиваться в вершине u1. Если этот маршрут будет содержать все дуги орграфа, то он будет искомым.Рис. 2.10Предположим, что в орграфе остались дуги, не вошедшие в маршрут L1. Рассмотрим дугу (u2, v1), причем u2принадлежит L1, av2 не принадлежит L1. В орграфе существует маршрут, соединяющий вершины v2 и u2. Вместе с дугой (u2, v2) он будетобразовывать маршрут L2 ,который начинается и оканчивается в вершине v2. Объединим маршруты L1и L2в один маршрут L(см. рис. 2.10). (Возможно, что маршруты имеют общие ребра.)Если маршрут Lне содержит все дуги орграфа G, то увеличим его с помощью некоторого маршрута L3, и так до тех пор, пока не получим нужный маршрут. Этот маршрут и будет соответствовать маршруту патрулирования.Домашняя работаЗадача № 11В одном государстве некоторые города соединены дорогами с односторонним движением. Оказалось, что при появлении любой новой дороги с односторонним движением между городами, которые до зтого не были соединены дорогами, стало возможным добраться из любого города в любой другой, не нарушая правил. Докажите, что такая возможность была и до появления новой дороги.Решение.Города и дороги государства задают ориентированный граф G. Новый орграф, получившийся из Gдобавлением дуги между любыми несмежными вершинами, является сильносвязным. Необходимо доказать, что орграф Gтакже сильносвязный. Пусть в орграфе Gсуществуют вершины uи v, не соединенные путем. Из условия задачи следует, что после добавления дуги (w1,w2), которой не было в орграфе G, в получившемся орграфепоявляется путь L1= (u,..., w1,w2, а, Ь,..., v) из вершины uв вершину v. Но путь L2= (u, с, d,..., w2, w1,..., v) из uв vпоявляется и при добавлении дуги (w2, w1). Тогда путь L= (u, с, d,..., w2, a, b,..., v) соединяет вершины uи vв орграфе G, что противоречит начальному предположению.Следовательно, в орграфе G любая вершина v достижима из любой вершины u, и орграф G сильносвязный. Задача №7B классе 30 человек. Каждому нравятся ровно kучеников1 из класса. При каком минимальном kможно утверждать, что обязательно найдутся два человека, которые нравятся друг другу?Решение.Как в предыдущей задаче, опишем симпатии школьников ориентированным графом. Если полустепень исхода к каждой вершины равна 15, то орграф содержит 30•15=450 дуг. В то же время в орграфе 30• 29/2 = 435 пар вершин. Поэтому хотя бы одна пара должна быть соединена двумя противоположно направленными дугами. Школьники, соответствующие этим вершинам, испытывают взаимные симпатии. Покажем, что k=15 является минимальновозможным числом. Пример для k15 строится так: расположим все вершины по кругу, после чего будем считать, что дуги идут из вершины ровно в kвершин, следующих за ней по часовой стрелке. Занятие № 3Односторонний орграф. Конденсация орграфа.Задача № 13B стране несколько городов. Между некоторыми из них в одном направлении летают самолеты. Известно, что для двух любых городов А и В можно (используя, если нужно, рейсы между другими городами) или долететь из А в В, или долететь из В в А. Докажите, что Рис. 2.11в этой стране можно, вылетев из некоторого города, побывать во всех остальных. Решение.Построим орграф авиалиний, в котором вершины будут обозначать города,а дуги —авиалинии между ними.Орграф называется односторонним, если для любых вершин по крайней мере одна достижима из другой. По условию задачи построенныйорграф является односторонним.Теорема: Граф является односторонним тогда и только тогда, когда в нем есть маршрут, содержащий все вершины орграфа.Доказательство. Необходимость.Рассмотрим маршрут в орграфе L=(v1, v2,..., vk), содержащий наибольшее число вершин. Так как для любых трех вершин орграфа хотя бы из одной достижимы две другие, то k≥3. Если маршрут содержит все вершины орграфа, то теорема верна.Пусть существует вершина u, не входящая в L. Если вершина v1 достижима из вершины u, то в орграфе существует маршрут, содержащий больше вершин,чем маршрут L, что противоречит выбору L(см. рис. 2.11). То же произойдет, если вершина uдостижима из вершины vk. Предположим, что это не выполняется.Рассмотрим две соседние в маршруте Lвершины х и у. Если из одной из них (например, вершины х) достижима вершина u, а вторая достижима из u, то в орграфе есть маршрут L1=(v1,...,x,...,u,...,y,...,vk), содержащее большее число вершин, чем L(см. рис. 2.12).Пусть это не выполняется. Тогда в орграфе снова существует маршрут L2=(v1,..., u,..., v2,..., vk) или L3=(v1..., vk1,...,u,...,vk) с большим числом вершин, чем L(см. рис. 2.13). Достаточность очевидна.Теорема доказана.Из теоремы следует существование в стране нужного маршрута облета городов.Рис. 2.12Рис. 2.13Задача № 14В королевстве 30 городов,некоторые из них соединены дорогами, так что из любого города можно доехать в любой другой. Из каждого города выходит не менее двух дорог, и между двумя городами не более одной дороги. Для того чтобы добиться большей безопасности, король Людовик установилна дорогах одностороннее движение так, чтобы в каждый город входила и выходила хотя бы одна дорога. Тем не менее, некоторые города стали недостижимы для проезда из других. Однако король никогда не признаетсвоих ошибок. Чтобы исправить создавшееся положение, он приказал построить новые дороги с односторонним движением. Докажите, что достаточно построить не более 10 дорог.Решение.Города королевства, его дороги с установленным односторонним движением задают ориентированный граф G. Необходимо доказать, что к графу G можно так добавить не более 10 дуг, чтобы превратить его в сильный орграф.Сильносвязной компонентой называется максимальный по включению подграф орграфа, который является сильным. (Максимальный по включению подграф —это такой подграф, который не содержится в подграфе с теми же свойствами, но с большим числом вершин или ребер.)Пусть G1,G2,...,Gk—сильносвязные компоненты орграфа G. Конденсацией орграфа G называется орграф G*, вершины которого u1, u2,..., ukсоответствуют сильным компонентам орграфа G, и вершина u1соединена дугой с вершиной ujтогда и только тогда, когда в орграфе G есть дуга, выходящая из компоненты Gi, и заходящая в компоненту Gj.На рис. 2.14 изображен орграф G и его конденсация —орграф G*. Орграф G имеет 6 сильносвязных компонент: орграфы G1, порожденный вершинами (v1,v2,v3), G2
вершинами (v4, v5, v6), G3—вершинами (v7, v8, v9,v10), G4—вершинами (v11, v12, v13, v14), G6—вершинами (v16, v17), сильносвязная компонента G5состоит из вершины v15.Конденсацией сильносвязного орграфа является граф К1.Теорема. Конденсация любого орграфа не имеет контуров.Доказательство:Пусть G= (u0,..., ui,..., uj,..., u0) —контур в орграфе G*. Тогда для любой вершины vi
Gi
существует маршрут в любую вершина vj Gj, а из vjмаршрут в vi. Но это противоречит максимальности сильносвязных компонент. Теорема доказана.Рис. 2.14Сильносвязная компонента будет называться концевой, если в конденсации ей будет соответствовать или вершина с нулевой полустепенью исхода, или с нулевой полустепенью захода. Для графа G, соответствующего городам и дорогам с односторонним движением королевства, рассмотрим концевые компоненты. Поскольку для любой ее вершины в нее входит и выходит ровно одна дуга, и две вершины не могут соединятьдве дуги, то каждая концевая компонента состоит не менее, чем из трех вершин. Поэтому в орграфе неболее 10 концевых компонент. Занумеруем концевые компоненты и соединим некоторую вершину первой из них с некоторой вершиной второй, некоторую вершину второй с некоторой вершинойтретьей и т.д., некоторую вершину последней из них с некоторой вершиной первой. Добавив, таким образом, не более 10 дуг, получим сильный орграф. Добавленные дуги соответствуют дорогам, которые нужно построить.Задача № 15Король Людовик приказал так установить одностороннее движение на дорогах между городами своего королевства, чтобы из каждого города в любой другой можно было проехать не более чем по двум дорогам. Оказалось, что после закрытия любой дороги на ремонт из каждого города попрежнему можно проехать в любой другой. Докажите, что теперь для этого нужно не более трех дорог.Решение.Города королевства, его дороги с установленным односторонним движением задают сильный орграф G, в котором расстояние между любыми двумя вершинами не более двух. Рассмотрим орграф G1, который получается из графа G после удаления дуги (u,v). Поскольку по условию задачи орграф G1сильный, то из вершины uдолжна выходить хотя бы одна дуга (u,u0). Но в графе G, а значит uв G1, существует цепь (u0,w,v). Поэтому вершины uи vсоединяет цепь (u,u0,w,v), состоящая из трех дуг. Аналогично рассматривается случай, когда удаление дуги (u,v) разрушает некоторую цепь, состоящую из двух дуг. Дуги построенных цепей соответствуют нужным дорогам в королевстве.Задача № 16В королевстве более четырех городов. Король Людовик приказал так соединить каждые два города авиалиниями, по которым самолеты летают в одном направлении, чтобы из любого города в любой другой можно было перелететь с помощью не более двух авиарейсов. Докажите, что это можно сделать.Рис. 2.15Решение.Для решения задачи необходимо ориентировать ребра графа Кn(n�4), чтобы расстояние между двумя любыми вершинами получившегося орграфа оказалось не более двух. Требуемая ориентация ребер графов K3и К6 представлена на рис. 2.15.Схема перехода от ориентации Тn
графа Кn
к ориентации графа Кn+2указана на рис. 2.16. Для этой цели к орграфу Тnс вершинами v1, v2, ..., vnдобавим вершины vn+1 и vn+2и дуги (vn+1,v1), (vn+1,v2), ...,(vn+1,vn), (v1,vn+2), (v2,vn+2), …,(v3,vn+2),и (vn+2,vn+1). При n=4 требуемая ориентация невозможна. Построенная ориентация вершин графа определит направления авиарейсов между городами. Рис. 2.16
Ссылки на источники1.Мельников О.И., Занимательные задачи по теории графов. Минск: ТетраСистемс, 2001. С. 144.2.Березина Л.Ю., Графы и их применение. М.: Просвещение, 1979. С. 143.3.Уилсон Р., Введение в теорию графов. М.: Мир, 1977. С. 207.4.Конное В.В., Клековкин Г.А., Коннова Л.Я., Геометрическая теория графов. М.: Народное образование, 1999. С. 240.5. Коннова Л.Я., Знакомьтесь, графы. Самара: Издво Института повышения квалификации работников образования, 2001. С. 108.6. Горбачев Я.В., Сборник олимпиадных задач по математике. М.: Издво МЦНМО, 2004. С. 560.7. Мельников О.Я.,Современные аспекты обучения дискретной математике. Глава 7. Минск: БГУ, 2002. С. 120.8. Мельников О.Я., Куприянович В.В.,Использование графовых задач при самостоятельной работе для развития воображения школьников //Народная асвета. 2002. № 10. С. 3133.9. Мельников О.И.,Графы в обучении математики //Математика в школе. 2003. № 8. С. 6772.
Sorokina Anna Andreevnathe teacher of Maths, MBEI «Kotluban secondary school», Volgograd region Gorodischensky district s. Kotlubananna_sorokina_84@list.ruFeatures of teaching elective courses for seniors pupils «The oriented graphs and their applications»Abstract.The article is devoted to the methods of teaching the ellective course for seniors pupils “The oriented graphs and their applications” with applications.Key words: algebra, problem teaching, oriented graphs and their applications/
