изоморфизм графов

изоморфизм графов Ориентированные графы Определение 4.6. Полустепенью исхода  (захода) вершины  число  вершины  равен 1 как в   (соответственно   (заходящих в вершину  , так и в  .  графа    будем называть  ), равное количеству дуг графа, исходящих из  ). Вклад каждой петли, инцидентной вершине  ,              Очевидно, что для любого ориентированного псевдографа выполняется  равенство: .             Вершину  ­ истоком. , для которой   называют стоком, а у которой                На рис. 4.5 показан орграф, у которого  ,  , ,  ,  ,  . Вершина  стоком, а вершина   этого графа является   ­ истоком. Если граф не имеет ребер (т.е.  называетсяпустым или нуль­графом. ), то все его вершины изолированы, и он  Типы конечных графов  вершинами обозначают символом  ). Граф порядка n без ребер называется пустым и обозначается    Простой неориентированный граф, в котором любые две вершины соединены ребром,  называется полным. Полный граф с  граф  называется  тривиальным. Можно расширить полный граф до полного графа с  петлями, добавляя петлю в каждой вершине (рис.4.6).  В ориентированном полном графе имеются пары ребер, по одному в каждом  направлении, соединяющие любые две различные вершины.  (рис.4.2,  . Граф    Турниром называется орграф, любую пару вершин которого соединяет только одна дуга. Турнир отличается от полного ориентированного графа тем, что у него нет  противоположно направленных дуг., если степени всех его              Граф называется однородным (регулярным) степени  вершин одинаковые и равны  . Однородный граф степени 1  называется паросочетанием. Примерами однородных графов могут служить графы,  образованные вершинами и ребрами пяти первых правильных многогранников (или, так  их называют, платоновых тел): тетраэдра и куба (степени 3), октаэдра (степени 4),  додекаэдра (степени 3), икосаэдра (степени 5). Граф третьей степени  называют кубическим, он обладает рядом интересных свойств и, в частности, всегда  имеет четное число вершин. Три кубических графа изображены на рис.4.2.             Из выписанной выше формулы, связывающей число звеньев графа  его вершин, для случая однородного графа степени   (все  ), получим:  со степенями . Напоминаем, что  должно быть четным, и, следовательно, у любого однородного графа нечетной степени (и кубического тоже) всегда четное количество вершин.  ­ число вершин графа. Поэтому, если   нечетное число, то                Орграф называется однородным степени  одинаковые и равны  = . В этом случае = :  , если полустепени всех его вершин  . Здесь, как и раньше,   и   ­ число вершин и дуг графа.             Если множество вершин простого графа  можно разбить на два  непересекающихся подмножества (доли)  ребер, соединяющих вершины одного и того же подмножества, то такой граф  называется двудольным (иначе ­биграфом). Полный двудольный (у него каждая вершина из  . Граф   соединена с каждой вершиной из  ) и при этом не существует  ). обозначают символом   изображен на рис 4.13.  где   ( ,  ,  Части графов Еще раз напоминаем: любой граф есть совокупность множества вершин и множества  ребер, при этом ребра фиксируют имеющиеся взаимозависимости между вершинами.  Каждое ребро представляет конкретную пару вершин, между которыми установлена  такая взаимосвязь. Игнорируя взаимосвязь между какими­то двумя вершинами, мы темсамым ликвидируем (удаляем) соответствующее ребро.  Операция удаления ребер порождает новый граф, с теми же вершинами, но с меньшим  числом ребер. Если по каким­то соображениям отпадает необходимость принимать во  внимание определенную вершину графа, то ее следует удалить. Операция удаления  вершины графа более сложная. Кроме самой вершины необходимо еще удалить и все те  ребра графа, которые представляли связи удаленной вершины с другими вершинами  графа, т.е. все инцидентные ей ребра. , полученный в результате операций удаления вершин и (или) ребер  Граф  графа  , называется частью (иногда подграфом) графа  графа  являются одновременно вершинами и ребрами графа  случае говорят, что  . В этом  . Нуль­граф считается частью каждого графа.   будет ориентированным  . Все вершины и ребра  :   содержится в  Граф  или        неориентированным в зависимости от того, каким является граф  . , изображенный на рис 4.8, получен в результате операций удаления              Граф  ребра  результат операций удаления у того же графа   (этот граф задан на рис. 4.7), а граф   графа   вершины  . , показанный на рис. 4.9, есть   графа  . Часть     ­ некоторое подмножество множества вершин   называется подграфом, порожденным  Пусть  графа  (или индуцированным) множеством вершин  если ребрами  принадлежат  множества  подграф состоит из самой вершины   являются только те ребра множества  . Он получается из графа   и всех ребер, им инцидентных. Для единственной вершины   и из петель вершины  , оба конца которых   в результате удаления всех вершин  , если они имеются.  (вершинно­порожденным подграфом),  этотПодграфом, порожденным множеством ребер  подграфом),называют часть  множества ребер   графа   графа  , где  , а  есть множество всех вершин графа   ­ некоторое подмножество  , которые   (реберно­порожденным  являются концами ребер множества  удалением всех ребер множества  вершин получившейся части. . Такой подграф получается из графа   и последующего удаления всех изолированных                Часть  Так как в этом случае  некоторых (или даже всех) его ребер.  графа   называется его остовным подграфом  или суграфом.  , то суграф получается из графа   после удаления  Замечание. В некоторых работах понятия подграфа и части графа отождествляются,  хотя есть исследователи, занимающиеся теорией графов, которые эти понятия  различают, определяя подграф как часть, полученную в результате операции удаления у  графа некоторых его вершин. Они пользуются только понятиями части, суграфа и  подграфа (в указанном только что смысле). Заметим, что в этом случае любая часть  графа   есть суграф некоторого подграфа этого графа: вначале у исходного графа  удаляем все вершины, не входящие в часть  затем изымаем ребра найденного подграфа, которые не принадлежат   (вместе с инцидентными им ребрами), а    .             Звездный граф , определяемый вершиной  всех  nвершин графа  вершине.  и   ей смежных, а его ребрами будут все ребра, инцидентные этой  , состоит из самой вершины   графа              Для каждой части  единственная дополнительная часть графа  ребер  ребрам:  , которые не являются ребрами  .  существует   (дополнение)  , состоящая из всех  , и вершин, инцидентных этим              На рис. 4.10 видим граф  дополнение графа   для суграфа  . , который есть суграф полного графа  , и граф   ­и   ­ две части  . Сумма (объединение, наложение) этих частей    Пусть  есть часть, состоящая из всех ребер (и вершин, им инцидентных), которые принадлежат  или  графа  , или им обоим. Пересечением частей графа  , ребра которой являются ребрами   одновременно.  назовем часть  , или   и   и              Две части  а следовательно,  не имеют  и  общих  ребер,  и   не пересекаются по вершинам, если не имеют общих вершин,  и две части не пересекаются по ребрам, если у них нет общих ребер. Часть  дополнение   не пересекаются по ребрам, и  .  и ее  Изоморфизм графов Ранее было отмечено, что любой абстрактный граф идентичен, или, как говорят  математики, изоморфен некоторому геометрическому графу. При изображении  геометрических графов имеется большая свобода в размещении вершин и в выборе  формы соединяющих их ребер. Поэтому может оказаться, что один и тот же граф  представляется различными чертежами, разглядывая которые далеко не сразу можно  осознать, что они являются изображениями одного и того же графа. Такие  геометрические графы тоже называют изоморфными.             Изоморфизм графов формально определяется следующим образом.  и  Определение 4.7. Графы  взаимно однозначное соответствие между множествами их вершин   и  соединены ребрами в одном из графов в том и только том случае, когда  соответствующие им вершины соединены в другом графе. Если ребра ориентированы, то  и их направления также должны соответствовать друг другу.  изоморфны, если существует такое  , что вершины              Геометрический граф, изоморфный абстрактному графу, называют  егогеометрической реализацией.  и   изоморфны, то пишут  p  (тогда и  p ). Легко видеть, что              Если графы  отношение изоморфизма графов рефлексивно, симметрично и транзитивно и является  отношением эквивалентности. Следовательно, множество всех графов разбивается на  классы эквивалентности так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы, как правило, отождествляют, и их  можно изображать одним рисунком. Они могут различаться конкретной природой своих  элементов, но именно это и игнорируется при введении понятия «граф». Нетрудно  показать, что три графа, изображенные на рис. 4.2, изоморфны.Из определения следует, что изоморфные графы могут различаться лишь  обозначениями вершин и ребер, так как у них должно быть равное число вершин и ребер, соответствующие друг другу вершины обязаны иметь одинаковые степени и  полустепени, и, разумеется, совершенно все равно, какую геометрическую реализацию  графа выбирать для его изображения.               Оба графа на рис. 4.11 изоморфны, так как существует взаимно однозначное  соответствие  , сохраняющее смежность. Говорят, что граф  части графа  .  изоморфно вкладывается в граф  , если   изоморфен некоторой Замечание. Многие практические задачи приводят к необходимости распознавания  изоморфизма и изоморфного вложения сложных структур, заданных в виде графов. С  содержательной точки зрения изоморфизм графов структур означает тождественность  функционирования самих структур, что допускает в некоторых случаях замену одной  структуры другой, ей изоморфной. Однако для того чтобы выяснить, изоморфны ли два   попарных сравнений,  графа имеющие  а для распознавания изоморфного вложения графа   вершин, в граф  , у  которого  относительно небольшом количестве элементов в графах (порядка 100) решение задачи  об изоморфизме методом полного перебора практически не реально, необходимо  использовать для этой цели специальные методы.  вершин, в общем случае требуется выполнить  , имеющего   вершин, необходимо провести   сравнений. Поэтому даже при    Плоские и планарные графы Вообще говоря, не имеет значения, как нарисовать граф, поскольку все его изображения  являются изоморфными графами и несут одну и ту же информацию. Однако  встречаются ситуации, когда крайне важно, чтобы изображение графа на плоскости  удовлетворяло определенным требованиям. Например, в радиоэлектронике при  изготовлении микросхем печатным способом электрические цепи наносятся наповерхность изоляционного материала. А так как проводники не изолированы, то они не  должны пересекаться. Аналогичная задача возникает при проектировании  железнодорожных и иных путей, где нежелательны переезды. Определение 4.8. Геометрический граф назовем плоским графом, если он нарисован на  плоскости так, что все линии, изображающие его ребра, пересекаются только в точках,  соответствующих вершинам графа, т.е. любая точка пересечения таких линий есть  вершина, инцидентная ребрам, которые эти линии изображают. Любой граф,  изоморфный плоскому графу, называют планарным.             О планарных графах говорят, что они укладываются на  плоскости (имеют плоскуюукладку). Планарный граф можно уложить на плоскости, а  плоский граф ­ это граф, уже уложенный на плоскости. Плоский граф есть изображение  планарного графа, однако не каждое изображение планарного графа является плоским  графом.             Пример плоского графа приведен на рис. 4.12. Изоморфный ему полный граф  (рис.4.13), укладываемый на плоскости, имеет два пересекающихся ребра, поэтому  граф   не является плоским ­ он только планарный.    Куратовского, играющие  На рис 4.13. показаны графы Понтрягина ­ фундаментальную роль в теории планарности графов. Они не являются планарными  графами. Граф  являясь планарным графом (полные графы   ­ планарные), становится  планарным после удаления хотя бы одного его ребра. Второй (двудольный граф  является моделью известной задачи о трех домах и трех колодцах.  представляет собой полный граф наименьшего порядка, который, не  ,  ,  )  .Для приложений чрезвычайно важно найти и описать необходимые и достаточные  условия планарности графов. Следует отметить, что практическая проверка таких  условий, как правило, является достаточно сложной задачей. Однако разработаны  эффективные алгоритмы, позволяющие для любого заданного графа или найти его  плоскую укладку, или установить, что граф не планарен. Достаточно очевидны  следующие теоремы. Теорема 4.2. Любая часть (подграф) планарного графа есть планарный граф. Теорема 4.3. Плоский граф не должен иметь в качестве своей части  графыПонтрягина ­  Куратовского.  Куратовского, необходимо ввести понятие гомеоморфизма              Для того чтобы сформулировать широко известный критерий планарности  Понтрягина­ графов. Операция подразбиения ребра  удалении ребра  ,  показан граф до операции подразбиения ребра  получившийся в результате этой операции.  и добавлении двух новых ребер  , а на рис. 4.15 изображен граф,   соответственно. Здесь   ­ новая (дополнительная) вершина графа. На рис 4.14  и  ,  , образованного парой вершин   и  , состоит в   и  , отвечающих парам вершин  Два графа называются гомеоморфными, если они могут быть получены из одного и того же графа подразбиением его ребер. Фундаментальное значение в теории планарности  имеет критерий планарности Понтрягина­  Куратовского.  Теорема 4.4. Граф планарен тогда и только тогда, когда он не содержит частей,  гомеоморфных графам Понтрягина­ Куратовского.  Матричное представление графов Пусть  помеченного графа пронумерованы. Пусть   ­ помеченный граф, имеющий   вершин и   ребер. Вершины и ребра   ­ вершины графа, а   ­ его  ребра. Отношение инцидентности можно определить матрицей  , имеющей    строк истолбцов. Столбцы соответствуют ребрам графа, а строки ­ вершинам. Если  неориентированное ребро (звено)   инцидентно вершине  , то  . Когда  ориентированное ребро (дуга)   инцидентно вершине  , то  , если вершина    ­ начало дуги, и  , если вершина   ­конец этой дуги. Если ребро   является петлей и вершина  ей инцидентна, то  , для орграфа и неографа. Пусть ребро    (неважно,  что это ­ звено, дуга или петля) не инцидентно вершине , тогда  полученная таким образом, называетсяматрицей инцидентности графа. Каждый  помеченный граф может иметь только одну матрицу инцидентности, а всякая матрица  инцидентности полностью определяет соответствующий граф. . Матрица,    Матрицей смежности графа называют квадратную матрицу  и столбцам которой соответствуют вершины помеченного графа (первый столбец  (строка) отвечает первой вершине и т.д.), а ее элементы находятся по следующим  правилам. Для неориентированного графа  равно количеству ребер, инцидентных  вершинам с номерами   и  ориентированного графа  . Петле в вершине i соответствует   равно   размера  , строкам . Для  количеству  вершины  и заходящих в вершину  . Петле в вершине i орграфа соответствует  .  ребер, выходящих из  Пример 4.2. Неориентированный граф, изображенный на рис. 4.16, имеет следующие  матрицы инцидентности (матрица  ) и смежности  (матрица  ):      Пример 4.3. Орграф, изображенный на рис. 4.17, имеет следующие матрицы  инцидентности (матрица  ) и смежности  (матрица  ):Графы Содержание 1 Основные понятия 2 Маршруты, цепи и циклы 3 Раскраска, плоские графы 4 Комбинаторные задачи на графах Литература В этом разделе курса мы рассматриваем понятие графа. В последнее время теория  графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Это проблемы проектирования интегральных схем и схем  управления, исследования автоматов, логических цепей, блок­схем программ,  экономики и статистики, химии и биологии, теории расписаний и дискретной  оптимизации. 1 Основные понятия Прежде всего рассмотрим способы задания графа и дополним  определения, данные в  разделе ``алгебраические системы''. В дальнейшем, если это явно не оговаривается, мы будем рассматривать только  простые графы.Способы задания графа 1. Явное задание графа как алгебраической системы. 2. Геометрический 3. Матрица смежности 4. Матрица инцидентности Рассмотрим различные способы задания для одного и того же графа. 1. <{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>. Так как мы  рассматриваем только простые графы, граф нам проще определять как модель,  носителем которой является множество вершин, а отношение – бинарное  отношение смежности вершин. Тогда данный граф запишется как  <{a,b,c,d}; {(a,b), (b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)}>. В таком представлении  ребру соответствуют две пары вершин (v1,v2) и (v2,v1), инцидентных данному  ребру. Чтобы задать такое представление, достаточно для каждого ребра указать  двухэлементное множество вершин – его мы и будем отождествлять с ребром. Для данного графа рёбра задаются множеством {{a,b},{b,c},{a,c},{c,d}} и граф мы  будем записывать как пару (V,E), где V – множество вершин, а E – множество  рёбер. В дальнейшем мы будем опираться именно на второе определение графа. 2. Геометрический 3. Матрица смежности a b c d a 0 1 1 0 b 1 0 1 0c 1 1 0 1 d 0 0 1 0 4. Матрица инцидентности u v w x a 1 0 0 0 b 1 1 1 0 c 0 1 0 1 d 0 0 1 1 Понятие изоморфизма для графов имеет наглядное толкование. Представим рёбра  графов эластичными нитями, связывающими узлы – вершины. Тогда, изоморфизм можно  представить как перемещение узлов и растяжение нитей. Пример 1 (изоморфизм). Покажем, что следующие два графа изоморфны. Действительно, отображение a ® e, b ® f, c ® g, d ® h, являющееся изоморфизмом легко  представить как модификацию первого графа, передвигающую вершину d в центр  рисунка. Демонстрация изоморфизма. 1.1 Постройте изоморфизм графов (cid:127)Определение 1 (Степень вершины). Степенью вершины назовём удвоенное количество петель, инцидентных этой вершине  плюс количество остальных инцидентных ей рёбер. 1.2 Докажите, что изоморфизм сохраняет степени вершин графа. Иначе говоря,  степень образа вершины при изоморфизме совпадает со степенью самой вершины. 1.3 Проверьте, изоморфны ли графы. см. Указания 1.4 Докажите, что сумма всех степеней вершин графа равна удвоенному количеству  рёбер. 1.5 Докажите, что в любом графе количество вершин нечётной степени – чётное  число. см. Указания Подграфы Определение 2 (Подграф). Подграфом графа называется граф, являющийся  подмоделью исходного графа. Иначе говоря, подграф содержит некоторые вершины  исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф). Определение 3 (Подграф, порождённый множеством вершин). Подграфом, порождённым множеством вершин U называется подграф, множество  вершин которого – U, содержащий те и только те рёбра, оба конца которых входят в U.Определение 4 (Остовной подграф). Подграф называется остовным подграфом, если  множество его вершин совпадает с множеством вершин самого графа. Два последних определения дают два вида максимальности подграфов: максимальность  множества вершин и максимальность множества рёбер. Это подтверждают следующие  три задачи: 1.6 Докажите, что подграф H графа G является порождённым множеством своих  вершин тогда и только тогда, когда не существует ни одного другого подграфа графа G, для которого H являлся бы остовным подграфом. см. Решение 1.7 Докажите, что подграф H графа G является остовным тогда и только тогда,  когда не существует ни одного другого подграфа графа G, для которого H являлся  бы подграфом, порождённым множеством своих вершин. 1.8 Докажите, что если подграф является остовным подграфом и подграфом,  порождённым множеством своих вершин одновременно, то этот подграф – сам  граф. Определение 5 (Пустой, полный графы). Пустым называется граф без  рёбер. Полным называется граф, в котором каждые две вершины смежны. 1.9 Докажите, что граф является пустым тогда и только тогда, когда все его  подграфы – тоже пустые. 1.10 Докажите, что граф является полным тогда и только тогда, когда все его  подграфы, порождённые некоторым множеством вершин – тоже полные. 1.11 Докажите, что полные (пустые) графы изоморфны тогда и только тогда,  когда они имеют одинаковое количество вершин. 1.12 Докажите, что пустой граф с n вершинами содержит ровно n попарно  неизоморфных подграфов. 1.13 Докажите, что граф с n вершинами является пустым тогда и только тогда,  когда он содержит ровно n попарно неизоморфных подграфов. 1.14 Докажите, что полный граф с n вершинами содержит ровно n попарно  неизоморфных подграфов, порождённых некоторыми множествами вершин.1.15 Докажите, что граф с n вершинами является полным или пустым тогда и  только тогда, когда он содержит ровно n попарно неизоморфных подграфов,  порождённых некоторыми множествами вершин. 2 Маршруты, цепи и циклы Маршруты, цепи и циклы Определение 6 (Маршрут). Маршрутом в графе G =  называется  последовательность вершин и рёбер вида v0,e1,v1,e2, ..., vn­1,en,vn, где vi О V,  i О [0,n], ei О E, (vi­1,ei), (vi,ei) О I, i О[1,n]. Вершины v0, vn называются связанными  данным маршрутом (или просто связанными). Вершину v0 называют началом, а vn –  концом маршрута. Если v0 = vn, то маршрут называютзамкнутым.  Число n называется длиной маршрута. Определение 7 (Цепь, простая цепь, цикл). Маршрут, в котором все рёбра попарно  различны, называется цепью. Замкнутый маршрут, являющийся цепью,  называется циклом. Маршрут, в котором все вершины попарно различны,  называется простой цепью. Цикл, в котором все вершины, кроме первой и последней,  попарно различны, называется простым циклом. Пример 2 (цепь). Маршрут a,{a,b},b,{b,c},c,{c,a},a,{a,d},d в первом графе из  примера 1 является цепью, но не является простой цепью. Замечание. Мы будем отождествлять циклы, являющиеся циклическими  перестановками друг друга. 2.1 Докажите, что изоморфизм сохраняет циклы графа. 2.2 Вернитесь к задаче 1.3 и получите для неё более простое решение. см. Указания Графы часто используют для изображения различных отношений (например,  иерархических отношений, т.е., на языке математики –  отношений частичного порядка). Правда, для точного представления таких графов необходимо выразить  понятие направления на графе. Мы не будем сейчас вводить новые понятия, а будем  просто использовать расположение вершин на рисунках (одна выше или ниже другой). Пример 3 (граф отношения делимости). Построим граф, изображающее отношение  делимости на множестве {1,2,3,4,5,6,7,8,9,10}. Принцип такой: если от одного числа до  другого есть цепь, ведущая вверх, тогда второе число делится на первое. (cid:127)Связность графа Определение 8 (Связность). Граф называется связным, если любая пара его вершин  связана. 2.3 Покажите, что отношение связанности вершин является отношением  эквивалентности. см. Указания Определение 9 (Связные компоненты). Связными компонентами графа называются  подграфы данного графа, вершины которых являются классами эквивалентности  отношения свзанности в данном графе. 2.4 Докажите, что связная компонента является связным графом. Определение 10 (Цикломатическое число). Цикломатическим числом графа  называется число связных компонент графа плюс число рёбер минус число вершин. Эйлеровы и гамильтоновы циклы Определение 11 (Эйлеров цикл). Эйлеровым называется цикл, проходящий по  каждому ребру графа ровно один раз. Граф, имеющий эйлеров цикл, тоже будем  называть эйлеровым. Пример 4 (эйлеров цикл). Построим эйлеров цикл для второго графа из задачи 1.1.  Это h, {h,l}, l, {l,i}, i, {i,m}, m, {m,j}, j, {j,n}, n, {n,k}, k, {k,h}, h, {h,i}, i, {i,j}, j, {j,k},  k, {k,l}, l, {l,m}, m, {m,n}, n,{n,h}, h. Демонстрация эйлерова цикла. (cid:127) (cid:127)Теорема 1 (Критерий эйлеровости графа). Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин – чётные числа. Требование связности в теореме естественно – несвязный граф может быть эйлеровым  только в том случае, если только одна связная компонента содержит рёбра.* см. Доказательство 2.5 Какие из графов, упоминающихся в задачах и примерах являются эйлеровыми ? Кроме понятия эйлерова цикла в задачах часто возникает необходимость нахождения  цепи, проходящей по каждому ребру ровно один раз (снимается требование замкнутости. Такие цепи будем называть эйлеровыми цепями. 2.6 Докажите, что в связном графе существует эйлерова цепь тогда и только  тогда, когда граф содержит не более двух вершин нечётной степени. см. Указания Определение 12 (Гамильтонов цикл). Гамильтоновым называется цикл, проходящий  по каждой вершине графа ровно один раз. 2.7 Все ли графы, упоминающиеся в задачах и примерах содержат гамильтонов  цикл ? 2.8 Содержит ли гамильтонов цикл граф ромбического додекаэдра: Деревья Определение 13 (Дерево). Связный граф без циклов называется деревом.Деревья особенно часто возникают на практике при изображении различных иерархий.  Например, популярны генеологические деревья. Пример 5 (генеологическое дерево). На рисунке показано библейское генеологическое  дерево. 2.9 Докажите, что граф является деревом тогда и только тогда, когда любая пара  различных вершин соединена единственной цепью. 2.10 Докажите, что граф является деревом тогда и только тогда, когда он связен,  но после удаления любого ребра становится несвязным. 2.11 Докажите, что количество рёбер дерева на единицу меньше количества  вершин. см. Указания Определение 14 (Лес, листья). Граф без циклов называется лесом. Вершины степени 1  в дереве называются листьями. 2.12 Докажите, что связными компонентами леса являются деревья. 2.13 Докажите, что цикломатическое число леса равно нулю. см. Указания Деревья – очень удобный инструмент представления информации самого разного вида.  Деревья отличаются общего случая от простых графов тем, что при обходе дерева  невозможны циклы. Это делает графы очень удобной формой организации данных для  различных алгоритмов. Таким образом, понятие дерева активно используется в  информатике и программировании. 2.14 Найдите количество остовных подграфов, являющихся деревьями, в полных  подграфах с 3­мя, 4­мя, 5­ю, 6­ю вершинами. см. Указания 3 Раскраска, плоские графы Раскраска графов (cid:127)Определение 15 (Раскраска). Раскраской графа G = (V,E) называется отображение c:  V ® N . * Определение 16 (Правильная раскраска). Раскраска называется правильной, если  образы любых двух смежных вершин различны: c(u) № c(v), если  (u,v) О I. Хроматическим числом графа называется минимальное количество красок,  необходимое для правильной раскраски графа. Пример 6 (раскраска). На следующем рисунке показана правильная раскраска. 3.1 Найдите хроматические числа графов, упоминающихся в задачах и примерах. 3.2 Докажите, что если в графе все циклы имеют чётную длину, то существует  правильная раскраска этого графа в 2 краски. 3.3 Докажите, что для любого дерева хроматическое число не превосходит 2. 3.4 Покажите, что необходимым условием существования гамильтонова цикла в  графе с хроматическим числом равным 2 является равенство количества вершин,  раскрашенных в разные краски. 3.5 Вернитесь к задаче 2.8 (о ромбическом додекаэдре) и получите её решение исходя  из предыдущей задачи. Грани графа Помимо использования в дискретной математике, графы находят применение и в  непрерывной математике, особенно в топологии. При этом графы представляют  геометрические объекты на некоторой поверхности (часто на плоскости или на  поверхности сферы.) Определение 17 (Плоский граф). Существует правило изображение графов на  поверхности: рёбра графа должны пересекаться только своими концами, то есть в  точках, представляющих вершины графа. (cid:127)Для графа, который может быть изображён подобным образом на плоскости, существует название: плоский граф. Определение 18 (Грань графа). Гранью графа, изображенного на некоторой  поверхности, называется часть поверхности, ограниченная рёбрами графа. Данное понятие грани, по­существу, совпадает с понятием грани многогранника. В  качестве поверхности в этом случае выступает поверхность многогранника. Если  многогранник выпуклый, его можно изобразить на плоскости, сохранив все грани. Это  можно наглядно представить следующим образом: одну из граней многогранника  растягиваем, а сам многогранник ``расплющиваем'' так, Изоморфизм, гомоморфизм и автоморфизм графов Для ориентированного графа   дуг можно рассматривать как график  бинарного отношения непосредственной достижимости, заданного на множестве вершин.  множество  В неориентированном графе  неупорядоченных пар. Для каждой неупорядоченной пары  вершины  и   и   связаны симметричным бинарным отношением  .  можно считать, что , то есть     множество   ребер является множеством  Таким образом, с каждым неориентированным и ориентированным графом связано  бинарное отношение  . Это отношение будем называть отношением смежности. С алгебраической точки зрения как ориентированный, так и неориентированный граф  можно рассматривать как модель, сигнатура которой состоит из одного бинарного  отношения:  . В классической теории графов изучаются преимущественно  конечные модели такого рода.При указанном подходе различия между ориентированным и неориентированным  графами проявляется только в свойствах отношения смежности  симметрично, то граф называют неориентированным, и с этой точки зрения  неориентированный граф можно считать частным случаем ориентированного. . Если это отношение  Примечание. При таком подходе в неориентированном графе могут быть петли, если  отношение  рефлексивным.  содержит некоторые элементы диагонали, в частности является  Применяя к данному частному случаю моделей общие понятия гомоморфизма и  изоморфизма, мы можем сформулировать следующие определения. Определение 5.14. Отображение  в множество вершин графа  в граф  отображении   множества вершин графа    называют гомоморфизмом графов (графа    ), если для любых двух вершин, смежных в первом графе, их образы при   смежны во втором графе, т.е. если Биективный гомоморфизм  тогда и только тогда, когда их образы смежны во втором графе, т.е. , такой, что любые две вершины смежны в первом графе  называют изоморфизмом графов   и  изоморфными, что записывают в виде   (графа  .  на граф  ), а графы   и   —Гомоморфизм графов, который является эпиморфизмом, называется также  гомоморфизмом одного графа на другой. Возвращаясь к нашему определению графа посредством двух множеств: множества  вершин  гомоморфизма и изоморфизма. , получим следующие варианты определений   и множества ребер (дуг)  Гомоморфизм неориентированного графа   в неориентированный  граф  , что для любых двух вершин  первого графа, соединенных ребром, их образы при отображении h также соединены  ребром, т.е.  есть такое отображение  Гомоморфизм ориентированного графа  граф  первого графа, таких, что есть дуга, ведущая из  в   есть такое отображение  , т.е.  в ориентированный  , что для любых двух вершин     в  , из вершины   тоже ведет дуга  Изоморфизм неориентированного графа  биекция  только тогда, когда соединены ребром их образы  , при которой две вершины   и   графа   и   на неориентированный граф   есть такая   соединены ребром тогда и  , т.е.Аналогично изоморфизм ориентированного графа  такая биекция  дуга в вершину   тогда и только тогда, когда в ориентированном графе  вершины  , при которой в ориентированном графе   ведет дуга в образ   на ориентированный граф   из вершины   вершины  , т.е.  из образа   есть   ведет    Пример 5.12. а. На рис. 5.29 отображение  , где       есть гомоморфизм ориентированного графа   в ориентированный  граф  . Обратим внимание на петлю  как  прообраза в   и  . : эта петля является образом дуги  , так  . В противоположность этому петля  не имеет  На этом же рисунке более толстыми стрелками выделен подграф  порожденный подмножеством вершин  образом графа  , получим (для того же подмножества  вершин) порожденный подграф, являющийся строгим гомоморфным образом графа  . Удаляя петлю в вершине  , Этот подграф будет гомоморфным   графа  ,  .Отметим, что каждая дуга в строгом гомоморфном образе ориентированного графа  имеет прообраз в  . б. На рис. 5.30 неориентированный граф  (если рассматривать неориентированные графы без петель).  есть строгий гомоморфный образ графа   (петли  в. На рис. 5.31 отображение h не является гомоморфизмом  но  , хотя  сообразить, что любой двухвершинный гомоморфный образ графа  иметь петлю, и, следовательно,  отображении.  не является гомоморфным образом   нет);      ,   на  , поскольку   и т.д. Легко   на рис. 5.31 должен  ни при каком  г. На рис. 5.32 изображен один граф из множества двухвершинных гомоморфных  образов  . д. Графы, изображенные на рис. 5.33, изоморфны, и изоморфизмом является, например,  отображение  , такое, чтоДополнения графов Зачастую для того, чтобы распознать изоморфизм графов, удобно перейти от исходных  графов к их дополнениям. Определение 5.15. Неориентированный (ориентированный) граф  дополнением неориентированного [ориентированного) графа  дополнение множества  на  .  до множества всех неупорядоченных [упорядоченных пар)  называют  , где   —  Можно доказать, что графы изоморфны тогда и только тогда, когда изоморфны их  дополнения. Например, перейдем к дополнениям графов, изображенных на рис. 5.33.  Анализ указанных дополнений (рис. 5.34) позволяет сразу обнаружить их изоморфизм, а  следовательно, и изоморфизм исходных графов. Более сложные случаи распознавания изоморфизма (главным образом, для  неориентированных графов) будут рассмотрены в последующей лекции.Автоморфизм графов Определение 5.16. Автоморфизм графа  множества его вершин, являющаяся изоморфизмом  на себя.  — это любая подстановка  Можно показать, что композиция двух любых автоморфизмов графа снова есть  автоморфизм этого графа, а подстановка, обратная к автоморфизму, опять­таки есть  автоморфизм. Таким образом, множество всех автоморфизмов данного графа образует  группу по операции композиции, которая является подгруппой симметрической группы  множества вершин графа. Ее называют группой автоморфизмов данного графа. Рассмотрим некоторые примеры групп автоморфизмов. Для графа, изображенного на рис. 5.35,а, группа автоморфизмов порождается  транспозициями (1 4) и (2 3), что легко усматривается из анализа дополнения этого  графа (рис. 5.35,б). Очевидно, что группа автоморфизмов графа есть подгруппа группы  перестановок множества его вершин. Поэтому, согласно теореме 2.13 Лагранжа,  порядок группы автоморфизмов графа есть делитель факториала числа его вершин. В  частности, для графа на рис. 5.35, а группа автоморфизмов имеет порядок 4 и состоит из тождественной подстановки   и подстановок  делится на 4. . Очевидно, что 4!Можно доказать, что автоморфизмы неориентированного графа сохраняют степени, а  ориентированного графа — полустепени исхода и захода всех его вершин. Это свойство  позволяет упростить описание автоморфизмов графа. Пример 5.13. Найдем нетривиальные (т.е. отличные от тождественной подстановки)  автоморфизмы неориентированного графа, изображенного на рис. 5.36. Так как среди  вершин графа лишь одна вершина  степень 2, то при любом изоморфизме эти вершины перейдут в себя. Значит, при  изоморфизме возможны лишь перестановки вершин   имеет степень 1 и лишь одна вершина   имеет   и  .  этого графа  Итак, для любого автоморфизма  то  всегда  нетривиальным автоморфизмом данного графа будет транспозиция  квадрата  , и, следовательно, поскольку  — единственная вершина, смежная с  , т.е. вершина   переходит в себя. Таким образом, единственным   относительно диагонали  . . Поскольку  ,  ,   — "отражение"  Иногда группу автоморфизмов графа легко найти именно из чисто геометрических  соображений при удачном изображении графа. Автоморфизм есть не что иное, как  преобразование графа (геометрической фигуры), при котором граф совмещается с  самим собой. Поэтому группу автоморфизмов графа можно изучать, анализируя его как  геометрическую фигуру.Пример 5.14. Для графа, изображенного на рис. 5.37, из геометрических соображений  вытекает, что автоморфизм  вокруг центра тяжести треугольника   сводится к повороту графа на 60° по часовой стрелке  . Следовательно, группа автоморфизмов порождается подстановкой  композицией трех циклов: , являющейся  Заметим, что ни один цикл, входящий в  графа. Так, если мы рассмотрим цикл , сам по себе не будет автоморфизмом данного  , то   и  , но  . В заключение сформулируем без доказательства теорему, доказанную Фрухтом в 1938 г.  и характеризующую все конечные группы в терминах групп автоморфизмов конечных  неориентированных графов. Теорема 5.5 (теорема Фрухта). Каждая конечная группа изоморфна группе  автоморфизмов конечного неориентированного графа ЭЙЛЕРОВЫ  И  ГАМИЛЬТОНОВЫ  ГРАФЫ      Эйлеровым циклом (путем) графа называется цикл (путь), содержащий все ребра  графа ровно один раз. Граф, обладающий эйлеровым циклом, называетсяэйлеровым  графом.     Теорема 14.4. Граф G обладает эйлеровым циклом с концами  только тогда, когда G  – связный и  степени. ,  –  единственные его вершины нечетной   и   тогда иТеорема 14.5. Граф G является эйлеровым тогда и только тогда, когда G –  связный и все его вершины имеют четную степень.        Гамильтоновым циклом (путем) графа G называется цикл (путь), проходящий  через каждую вершину G в точности по одному разу. Граф, обладающий гамильтоновым  циклом, называется гамильтоновым. Критерий существования гамильтонова цикла в  произвольном графе G еще не найден. Достаточным условием существования  гамильтонова цикла является полнота графа G.         На рис. 14.5 граф G не является эйлеровым (вершина  ребру) и не является гамильтоновым, но обладает эйлеровым   инцидентна только одному путем  рис. 14.6 является эйлеровым (последовательность   с концевыми вершинами   и  . Граф изображенный на  ребер      МАТРИЦА  ГРАФОВ  образует эйлеров цикл).        Граф может быть задан  разными способами: рисунком, перечислением вершин и  ребер (или дуг) и т. д. Одним из самых удобных способов является задание  графа  с  помощью  матрицы. Пусть  некоторый  граф  G имеет n вершин     и  m  ребер   Каждая строка матрицы будет соответствовать вершине, а столбец – ребру графа. В  .  Построим   матрицу,   имеющую n строк и m столбцов.  столбце   все элементы, кроме двух, будут равны нулю. Для ориентированного графа в строке, соответствующей начальной вершине дуги  соответствующей конечной вершине, ­ число  –1. , ставят число +1, а в строке,Для неориентированного графа в строках матрицы, соответствующих концевым  вершинам ребра  называются матрицами  инциденций  графа. , ставят 1, а в остальных строках – 0. Построенные матрицы  ПОТОКИ  В  СЕТЯХ  некоторой сети       Сетью называется граф, элементам которого поставлены в соответствие некоторые  параметры. Далее элементы множества R будем называть узлами, а  множества  – дугами. Пусть  каждой  дуге   поставлено в  соответствие неотрицательное (действительное) число   называемое  пропускной  способностью  дуги   множество  способности. Пусть s и t – два различных узла из R. Стационарный поток  величины v из s в t в сети   множество неотрицательных чисел, удовлетворяющая линейным уравнениям и  неравенствам  в множество неотрицательных чисел, называется функцией пропускной   есть функция f, отображающая множество А  в  , отображающая    ,   . Функция  (14.4) (14.5) где   («после x»),  («перед х»).         Будем называть узел s – источником, узел t – стоком, а остальные узлы  – промежуточными.        Если   дан   поток   f,   то   число   или потоком по дуге  (14.5), вопрос о существовании потока не возникает. Система уравнений (14.4)  избыточна, так как складывая все строки ее матрицы, мы получаем нулевой вектор.  Таким образом, не нарушая общности, можно отбросить одно из уравнений системы.    называется   дуговым   потоком   и   удовлетворяют условиям (14.4) и  . Поскольку            Потоком в сети  ребру   сети целое число   назовем функцию f, сопоставляющую каждому   и обладающую следующими свойствами: