Связность. Компоненты связности.
Определение 8.1.
Две вершины графа А и В называются связными, если существует путь с концами А и В.
Определение 8.2.
Граф называется связным, если каждые две вершины его связные, иначе, если любая пара его вершин соединяется цепью. Граф называется несвязным, если хотя бы две вершины несвязные.
Если граф не связан, то его можно разбить на подграфы так, что все вершины в подграфе будут связаны, а вершины из различных подграфов не связаны. Такие подграфы называются компонентами связности графа.
Определение 8.3.
Максимально возможный связный подграф графа G называется компонентой графа G.
Несвязный граф имеет по крайней мере две компоненты.
Определение 8.4.
Ребро (А,В) называется мостомграфа G, если в графе, полученном после удаления из графа G ребра (А,В) вершины А и В оказываются несвязными.
Деревья. Лес.
Определение 9.1.
Всякий связный граф, не имеющий циклов, называется деревом. Определение 9.2.
Несвязный граф, каждая компонента которого является деревом, т.е. представляющий собой объединение деревьев, называется лесом.
Определение 9.3. Вершина называется изолированной, если степень ее равна нулю. Если степень вершины дерева равна единице, то она называется висячей вершиной.
В примере висячими являются вершины a , b , c , d , e , f , g .
Дерево с р вершинами содержит р –1 ребер.
Многие графы, употребляемые в приложениях, являются деревьями. Например, графы всевозможных сортировок и классификаций. Корреспонденцию, пришедшую в страну, сортируют сначала по городам. Затем, в каждом городе – по отделениям связи, там – по участкам и т.д. Подобно этому живые организмы классифицируют сначала по типам, внутри типа – по классам, затем – по порядкам и т.д.
|
|
|
Деревьями являются и всевозможные схемы идентификаций, например, в аналитической химии при качественном анализе пользуются деревом, вершинами которого являются некоторые стандартные тестовые реакции. Выбор ребра, по которому надо двигаться из данной вершины, определяется поведением исследуемого вещества в соответствующей реакции (выпадение в осадок, помутнение и т.п.).
В физиологии рассматривают трахеобронхиальное дерево, вершинами которого являются участки раздвоения дыхательных путей, а ребрами – сами эти пути.
Наконец, деревьями являются всевозможные схемы происхождения: дерево языков, дерево происхождения видов, фамильное дерево и т.д.
Эйлеровы графы.
Мы уже говорили, что исторически теория графов (как и топология) зародилась при решении Эйлером головоломок, в которых требуется вычертить на плоскости росчерком замкнутые кривые, обводя каждый участок в точности один раз.
|
|
|
Определение 10.1.
Эйлеровым путем в графе называется путь, содержащий все ребра графа.
Определение 10.2.
Эйлеровым циклом в графе называется цикл, содержащий все ребра графа.
Определение 10.3.
Граф, обладающий эйлеровым циклом, называется эйлеровым графом.
Теорема. Если граф обладает эйлеровым циклом, то он связный.
Примеры эйлеровых графов:
1) план выставки, если экспонаты расположены по обеим сторонам залов, т.е. можно составить такой замкнутый маршрут, что по каждому залу посетитель сможет пройти в точности два раза – по одному с каждой стороны в разных направлениях.
2) Любой город можно обойти, пройдя по каждой улице ровно два раза – по одному в каждом направлении.
3) На рисунке изображена схема зоопарка. Вершины графа – вход, выход, перекрестки, повороты, тупики. Ребра – дорожки, вдоль которых расположены клетки. Найдите маршрут, по которому экскурсовод мог бы провести посетителей, показав им всех зверей и не проходя более одного раза ни одного участка пути.
|
|
|
Решение.
Способ обходить все ребра графа можно использовать, например, для отыскания пути, позволяющего выбраться из лабиринта. Если известно, что у лабиринта все «стенки» связаны друг с другом, т.е. нет замкнутых маршрутов, по которым можно возвращаться в исходную точку, то такой лабиринт всегда можно обойти весь, касаясь стенки одной рукой, например, правой.
Существует правило Тарри (французский математик) – правило обхода любого лабиринта – при обходе лабиринта следует, попадая в любой перекресток А впервые по некоторому пути а, при возвращении в этот перекресток А избегать пользоваться путем а до тех пор, пока это возможно; и лишь только в том случае идти по пути а в обратную сторону, когда все остальные пути из А будут пройдены дважды.
Теорема. Для того, чтобы связный граф (мультиграф) был эйлеровым, необходимо и достаточно, чтобы степени всех его вершин были четными.
Замечание. Данная теорема позволяет решить задачу о семи кенигсбергских мостах.
Планарные и плоские графы.
Среди изоморфных диаграмм одного и того же графа могут быть диаграммы с ребрами, пересекающимися не только в вершинах. Некоторыми из таких диаграмм легко заменить изоморфными, лишенными этого недостатка.
|
|
|
Определение 11.1.
Граф называется планарным, если его можно изобразить на плоскости диаграммой, ребра которой пересекаются только в вершинах.
Саму диаграмму называютплоским графом.
Одни графы можно нарисовать на плоскости так, чтобы их ребра не имели общих точек, кроме вершин им принадлежащим; другие так рисовать нельзя. В силу этого отдельные графы могут рассматриваться как географические карты, нанесенные на плоскость или сферу.
Определение 11.2.Если планарный граф односвязен, то его плоский граф называется картой.
Пример.
На рис. а) изображен не плоский граф. На рис. b) изображен тот же граф, только плоский.
На рис. с) изображен не планарный граф,
на рис. d) – изоморфный ему плоский граф – карта.
В отличие от географических карт плоский односвязный граф может иметь висячие вершины.
Рассмотрим карту некоторого графа.
Определение 11.3.
Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.
Пример.
На рис. а) (1,2,4,1) – не грань, так как она содержит внутри себя (1,2,3,1). Всего в графе четыре грани: (1,7.4,1), (1,4,2,3,1), (1,2,3,1), (2.6,5,4,2).
На рис.b) (1,2,3,4,1) – грань, так как ребро (4,5) не образует цикла.
Определение 11.4.
Цикл, охватывающий все внутренние грани, называется внешней границей карты. Множество точек плоскости, лежащих вне этого цикла, называется границей внешней грани.
Любому выпуклому трехмерному многограннику можно поставить в соответствие некоторую карту, ребра и грани которой, включая внешнюю, соответствуют ребрам и граням многогранника.
Список литературы
1. Андерсон Дж.А. Дискретная математика и комбинаторика. – М.: Вильямс, 2004.
2. Асанов М.О. Дискретная математика: графы, матроиды, алгоритмы: учебное пособие/ М.О. Асанов, В.А. Баранский, В.В. Расин. – СПб.: Лань, 2010.
3. Кузнецов О.П. Дискретная математика для инженера. – СПб.: Лань, 2007.
4. Лапшин А.Б. Дискретная математика и математическая логика. Ч.4. Элементы теории графов/ А.Б.Лапшин, О.Б. Садовская. – Кострома, Изд-во Костром. гос. технол. ун-та, 2005.
5. Нефедов В.Н. Курс дискретной математики: Учебпособие/ В.Н. Нефедов, В. А. Осипова. – М: Изд-во МАИ, 1992.
6. Палий И. А. Дискретная математика. Курс лекций/ И. А. Палий. – М.: Эксмо, 2008.
7. Редькин Н. П. Дискретная математика: Курс лекций для студентов - механиков: Учебное пособие. – СПб.: Лань, 2006.
8. Судоплатов С.В. Дискретная математика: Учебник/ С. В. Судоплатов, Е. В. Овчинникова. – М.: ИНФРА - М; Новосибирск: Изд-во НГТУ, 2007.
9. Шапорев С. Д. Дискретная математика. Курс лекций и практических занятий. – СПб.: БХВ - Петербург, 2006.
10. Шепелев Ю. П. Дискретная математика. Учебное пособие. – СПб.: Лань, 2008.
http://ci-plus-plus-snachala.ru/?p=1881
Дата добавления: 2021-03-18; просмотров: 70; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!