Графы и их применение

              

    ЗАДАЧА  О СОЕДИНЕНИИ ГОРОДОВ 

    

    Известны  точки, в которых предполагается разместить города, и известны трассы дорог, которые можно построить, а также стоимость строительства.

    На  рис. 7 указаны населенные пункты A, B, C, D, E, F; арабские цифры около проектируемых  участков дорог - стоимость их строительства (в условных единицах), римские цифры - номера дуг. Требуется определить, какие из дорог следует построить, так, чтобы: полученная схема дорог позволяла попасть из любого города в любой; из всех возможных схем имела наименьшую стоимость строительства.

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

    Определение 1. Взвешенным графом (графом с весами на дугах) будем называть четверку G (X, U, f, ρ), где G (X, U, f) – граф, ρ : U → (0, +∞).

     Отображением ρ называется весовым  отображением. Если u Є U, то ρ (u) называют весом дуги u. Если                 - путь или цепь на графе G, то ее весом называют величину

    

    Весом графа G (X, U, f, ρ) называют величину

    

    Сформулируем  задачу о соединении городов на языке теории графов.

    Дан конечный связный взвешенный граф G (X, U, f, ρ). Требуется найти связный частичный граф минимального веса.

    Покрывающее дерево связного графа - его частичный  граф, который является деревом. Если G не является связным графом, то говорят о покрывающем лесе, т.е. о деревьях, покрывающих его компоненты связности.

    Лемма. Решение задачи о соединении городов - покрывающее дерево.

    Предположим противное, т.е., что решение задачи не является деревом, тогда на нем существует хотя бы одна дуга, которая не является мостом. Обозначим ее u₀. Рассмотрим граф Очевидно, он связан и

     , что противоречит тому, что является решением задачи о соединении городов.

    Теорема (алгоритм Краскала).

    Последовательность  дуг покрывающего дерева минимального веса может быть найдена с помощью алгоритма:

    1) u₁ - дуга минимального веса из множества U, не являющаяся петлей.

    2) Если уже определен начальный  отрезок последовательности u₁, u₂, ..., u_k-1, то дуга u_k выбирается из множества U\{u₁,u₂,...,u_k-1} так, что выполнено два условия:

    а) добавление дуги u_k к {u₁,u₂,...,u_k-1} не приводит к образованию циклов

    б) из дуг, удовлетворяющих условию а), дуга u_k обладает наименьшим весом.

    Очевидно, что  Это дерево обозначим Т_Кр. Покажем, что Т_Кр является решением задачи о соединении городов. Предположим, что существует другое покрывающее дерево , при этом ρ (Т) ≤ ρ (Т_Кр). Упорядочим последовательность дуг дерева Т так, что и Обозначим через к такой индекс, что u₁ = ν₁, u₂ = ν₂, u_k-1 = ν_k-1, u_k ≠ ν_k. Тогда ρ(u_k) ≤ ρ(ν_k), так как ν_k удовлетворяет подпункту а) из пункта 2), а u_k удовлетворяет всему пункту 2). Добавим к дереву Т дугу u_k. Это привело к образованию единственного простого цикла, содержащего дугу  u_k. Очевидно, этот простой цикл содержит хотя бы одну дугу ν_j, j>k. Мы имеем ρ(u_k)≤ρ(ν_k)≤ρ(ν_j). Разорвем этот цикл, удалив дугу ν_j. Полученное дерево обозначим Т₁. Занумеруем его последовательность Так, что . Ясно, что ρ (Т₁) ≤ ρ (Т).

    Возможны 2 случая:

1. Тогда Т₁ = Т_Кр, и мы имеем ρ (Т) ≥ ρ (Т_Кр). (что является противоречием)
2. Обозначим через к₁ такой индекс, для которого

 

  Из  построения Т₁ следует, что к₁ > к. Тогда, повторяя рассуждения, приведенные для пары Т_Кр, Т, к паре Т_кр, Т₁, мы получим граф Т₂, k₂ > k₁, для которого опять возможны два случая: 1, 2. Но случай 1 приводит к противоречию, а случай 2 приведет к графу Т₃ и к₃ > k₂.

  Пример. Применим алгоритм Краскала к графу, приведенному на рисунке 7. На первом шаге выбирается дуга u1 = III, затем u2 = I, u3 = V (далее отпадает возможность выбора дуги IV), u4 = VIII (далее отпадает возможность выбора дуги VI), u5 = IX (далее отпадает возможность выбора дуг II, X, VII). Процесс выбора дуг автоматически оборвался. Покрывающее дерево минимального веса приведено на рис. 8.

  Пунктиром обозначены дуги, не вошедшие в это  дерево. ρ (Т_Кр) = 11. 

    
 
 
 
 
 
 
 
 
 
 
 
 

    ЗАДАЧА  О НАЗНАЧЕНИИ НА ДОЛЖНОСТЬ

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

    Продемонстрируем  задачу с помощью графа. Имеется  группа лиц, обозначим через М, и некоторое множество должностей, Р. Построим граф, проводя ребра (m,p), соединяющие каждого человека m из множества М с теми должностями р из множества Р, которые он может занять. Такой граф изображен на рис. 9

    

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

    Предположим, что общее число лиц, желающих получить работу, равно N. Для разрешимости задачи о назначениях на должности должно выполняться условие:

    Какую бы группу из к человек, к=1,2,...,N, мы ни взяли должно найтись  должностей, каждую из которых может занять хоть один из наших к претендентов (т.е. такие к работ, что с каждой из них справится наша группа к лиц).

    Например, если один из людей является плотником, а другой - и плотником и водопроводчиком и, если имеются два места водопроводчика, то условие выполняется при к=2, но не выполняется при к=1, и поэтому указанные лица не могут быть одновременно устроены на работу.

    Докажем достаточность этого условия.

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

    Теорема очевидна при N=1; если имеется один человек, годный хоть для одной работы, он может получить именно ее. При N=2 условие гарантирует, что найдутся по крайней мере две работы, для каждой из которых пригоден хоть один из двух лиц.

    Попытаемся  доказать теорему в общем случае методом математической индукции: предположим, что утверждение справедливо, если число людей не превосходит N-1, и докажем, что в таком случае оно верно и для N человек.

    Если  условие выполнено, оно может  выполняться с запасом или  в обрез, а именно может случиться, что каждая группа из к человек (к=1,2,...,N-1) вместе может выполнять больше чем к работ (условие выполняется с запасом), или может быть так, что для некоторого к₀ (к₀=1,2,...,N-1) имеется группа из к₀ людей, вместе пригодных в точности для к₀ работ (условие выполняется в обрез).

    Если  условие выполняется с запасом, выберем кого-нибудь из N человек  и поставим его на одну из работ, к которой он пригоден. Среди оставшихся N-1 людей каждые к человек вместе могут выполнять, по крайней мере, к работ, так как среди имевшихся вначале работ было по крайней мере к+1 работ, которые эти люди вместе могли выполнять, произведенное же назначение на место изъяло, самое большее, одну годную для них работу. По предложению индукции каждый из этих N-1 человек может быть обеспечен подходящей ему работой.

    Если условие выполняется в обрез, рассмотрим какую-нибудь группу А₀ из к₀ человек (к₀<N), вместе годных в точности для к₀ работ. В силу условия для каждых к из этих людей (при к=1,2,...,к₀) найдется не менее чем к подходящих работ. По предположению индукции к₀ человек множества А₀ могут быть обеспечены работой. Рассмотрим группу из N-k₀ оставшихся лиц. Покажем, что условие остается справедливым для них с учетом лишь оставшихся работ, то есть, что для каждой группы В, состоящей из к из этих лиц (при к=1,2,...,N-к₀), найдется еще, по крайней мере, к свободных мест, каждое из которых они могут занять.

    

    На  рис. 10 изображен граф для случая N=6. Первые три вершины из нижней линии представляют группу А₀ (при к₀=3) из троих людей, являющихся водопроводчиком (в), плотником и водопроводчиком (пв) одновременно, и плотником (п), а ребра идут к должностям (вершинам на верхней линии). Оставшиеся три вершины (N-k₀=3) представляют троих людей, готовых работать каменщиком (к), водопроводчиком (в) и штукатуром (ш). Условие не справедливо для группы В, состоящей из каменщика и водопроводчика, так как среди оставшихся вакантных мест нет места водопроводчика, а есть только каменщика. Условие не справедливо также и для множества А₀+В из пяти человек, так как имеются лишь четыре подходящие им должности.

    Упражнения. 

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

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

2. сколько кружков  из трех участников можно образовать в классе из 12 учеников? Могут ли все эти кружки иметь различных  старост?

Решение: Число кружков равно (12*11*10)/(1*2*3) = 220; оно намного больше числа возможных старост, равного 12. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    ГЕНЕАЛОГИЧЕСКИЕ ГРАФЫ 

     Рисуя родословное дерево, можно воспользоваться  ориентированным графом, чтобы показать на нем родственные отношения. Ориентированное  ребро (А,В), проводимое от члена семьи А к члену семьи В, указывает на то, что В является сыном или дочерью А.

Такие генеалогические графы обладают некоторыми свойствами. Одно из них состоит в том, что как каждый индивидуум имеет двух родителей, отца и мать, то у каждой вершины должно быть два входящих ребра, т.е. ρ(В)=2 (1).

     Основная  ячейка генеалогического графа состоит  из двух ребер, как на рис. 11, где В является потомком двух индивидуумов - отца О и матери М.

     

     Так как наши знания ограничены, наступит момент, когда неизвестны один или  оба родителя. Поэтому равенство (1) правильнее заменить: ρ(В)≤2 (2).

     Рис. 12 показывает, что В1, В2, В3 являются братьями и сестрами, т.к. все они дети одних и тех же родителей О и М.

 

     На  рис. 13 видно, что В4 является сводным  братом или сводной сестрой по отношению к В1, В2, В3 т. к. у них одна и та же мать М, но разные отцы О и О1.

 

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

     

     Пример (рис. 14) показывает, что это не всегда возможно. А1 относится к классу О. Тогда как его ребенок В1 является также ребенком А2, то А2 относится к классу М. Т.к. А2 и А3 имеют ребенка В3, то А3 также должно относится к О, что противоречит тому, что в соответствии с В2 является ребенком А1 и А3, каждый из которых относится к О.