Навигация
Основные понятия теории графов
49194
знака
0
таблиц
31
изображение
9. Основные понятия теории графов
Граф – система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (рис. 1).
Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным (рис. 1, А); граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным (рис. 1, Б).
Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Будем обозначать вполне несвязный граф с п вершинами через Nn; N4 показан на рис. 1. Заметим, что у вполне несвязного графа все вершины изолированы. Вполне несвязные графы не представляют особого интереса.
Простой граф, в котором любые две вершины смежны, называется полным графом. Полный граф с n вершинами обычно обозначается через 
. Графы 
и 
изображены на рис. 2 и 3. имеет ровно n (n – 1)/2 ребер.
Регулярные графы. Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом. Если степень каждой вершины равна r, то граф называется регулярным степени r. Регулярные графы степени 3, называемые также кубическими (или трехвалентными) графами (см., например, рис. 2 и 4). Другим известным примером кубического графа является так называемый граф Петерсена, показанный на рис. 5. Отметим, что каждый вполне несвязный граф является регулярным степени 0, а каждый полный граф Кn – регулярным степени n – 1.
Среди регулярных графов особенно интересны так называемые Платоновы графы – графы образованные вершинами и ребрами пяти правильных многогранников – платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра. Граф соответствует тетраэдру (рис. 2); графы, соответствующие кубу и октаэдру, показаны на рис. 5 и 6;
Двудольные графы. Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2 (рис. 7);
тогда G называется двудольным графом. Такие графы иногда обозначают G(V1,V2), если хотят выделить два указанных подмножества. Двудольный граф можно определить и по-другому – в терминах раскраски его вершин двумя цветами, скажем красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой – синий. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из V1 соединена с каждой вершиной из V2; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается 
где m, n – число вершин соответственно в V1 и V2. Например, на рис. 8 изображен
граф K4,3. Заметим, что граф имеет ровно m + n вершин и mn ребер. Полный двудольный граф вида 
называется звездным графом; на рис. 9 изображен звездный граф 
.
Связные графы. Граф связный, если его нельзя представить в виде объединения двух графов, и несвязный в противном случае. Очевидно, что всякий несвязный граф G можно представить в виде объединения конечного числа связных графов – каждый из таких связных графов называется компонентой (связности) графа G. (На рис. 10 изображен граф с тремя компонентами.) Доказательство некоторых утверждений для произвольных графов часто бывает удобно сначала провести для связных графов, а затем применить их к каждой компоненте в отдельности.
Циклические графы и колеса. Связный регулярный граф степени 2 называется циклическим графом (или циклом); циклический граф. с п вершинами обозначается через Сn. Соединение графов 
и (п ≥ 3) называется колесом с п вершинами и обозначается Wn. На рис. 11 изображены С6 и W6; граф W4 уже появлялся на рис. 2.
Эйлеровы графы
Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро; такая цепь называется эйлеровой цепью. Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым; при этом каждый эйлеров граф будет полуэйлеровым. На рис. 13,14,15 изображены соответственно не эйлеров, полуэилеров и эйлеров графы.
Название «эйлеров» возникло в связи с тем, что Эйлер первым решил знаменитую задачу о кенигсбергских мостах, в которой нужно было узнать, имеет ли граф, изображенный на рис. 15, эйлерову цепь (не имеет).
Примеры приложений теории графов
1. «Транспортные» задачи, в которых вершинами графа являются пункты, а ребрами – дороги (автомобильные, железные и др.) и / или другие транспортные (например, авиационные) маршруты. Другой пример – сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках.
2. «Технологические задачи», в которых вершины отражают производственные элементы (заводы, цеха, станки и т.д.), а дуги потоки сырья, материалов и продукции между ними, заключаются в определении оптимальной загрузки производственных элементов и обеспечивающих эту загрузку потоков.
3. Обменные схемы, являющиеся моделями таких явлений как бартер, взаимозачеты и т.д. Вершины графа при этом описывают участников обменной схемы (цепочки), а дуги – потоки материальных и финансовых ресурсов между ними. Задача заключается в определении цепочки обменов, оптимальной с точки зрения, например, организатора обмена и согласованной с интересами участников цепочки и существующими ограничениями
4. Управление проектами. (Управление проектами – раздел теории управления, изучающий методы и механизмы управления изменениями (проектом называется целенаправленное изменение некоторой системы, осуществляемое в рамках ограничений на время и используемые ресурсы; характерной чертой любого проекта является его уникальность, то есть нерегулярность соответствующих изменений.)). С точки зрения теории графов проект – совокупность операций и зависимостей между ними. Хрестоматийным примером является проект строительства некоторого объекта. Совокупность моделей и методов, использующих язык и результаты теории графов и ориентированных на решение задач управления проектами, получила название календарно-сетевого планирования и управления (КСПУ). В рамках КСПУ решаются задачи определения последовательности выполнения операций и распределения ресурсов между ними, оптимальных с точки зрения тех или иных критериев (времени проекта, затрат, и др.).
5. Модели коллективов и групп, используемые в социологии, основываются на представлении людей или их групп в виде вершин, а отношений между ними (например, отношений знакомства, доверия, симпатии и т.д.) – в виде ребер или дуг. В рамках подобного описания решаются задачи исследования структуры социальных групп, их сравнения, определения агрегированных показателей, отражающих степень напряженности, согласованности, взаимодействия и др.
6. Модели организационных структур, в которых вершинами являются элементы организационной системы, а ребрами или дугами – связи (информационные, управляющие, технологические и др.) между ними.
Список используемой литературы
1. «Основы графической информации» Н.А. Мишустин, Е.П. Жуленев. ВолгГТУ – Волгоград, 1998.
Похожие работы
... обязан планировать структуру тьюториалов, используя особые плановые инструменты. Они должны действовать так, чтобы студенты: · знали назначение, цели и проблемы конкретного тьюториала (желательно связанные с целями студентов) _________________________ _______________________________________________________________; · знали заранее, что они собираются достичь, выполняя то или иное задание/ ...
... и сообщений электронной почты, то сегодня решаются более сложные задачи распределенного доступа к ресурсам. Созданы оболочки, поддерживающие функции сетевого поиска и доступа к распределенным информационным ресурсам, электронным архивам. Internet, служившая когда-то исключительно исследовательским и учебным группам, чьи интересы простирались вплоть до доступа к суперкомпьютерам, стала популярной ...
... многих странах (в том числе развитых) применение компьютеров в управлении городскими территориями, ведении кадастра, анализе рыночных тенденций в рамках города весьма ограничено. В связи с этим выделим причины, по которым автоматизация решения типовых задач управления региональной недвижимостью Тульской области, как, впрочем, и других городов России, представляется весьма разумной: все материалы ...
... важной составной частью как денежного рынка, так и рынка капиталов, которые в совокупности составляют финансовый рынок. Цель функционирования рынка ценных бумаг -как и всех финансовых рынков - состоит в том, чтобы обеспечивать наличие механизма для привлечения инвестиций в экономику путем установления необходимых контактов между теми, кто нуждается в средствах, и теми, кто хотел бы инвестировать ...
0 комментариев