Комплектующие для игровых автоматов
Разработка игровых программ на заказ и др
novotechgi.com

Некоторые классы графов

7207
0
08 июля 2009
(38.3.) Большинство графов, которые используются в приложениях (например, графы сортировок, классификаций) предполагают наличие диаграмм, именуемых деревьями. Связный неориентированный граф без циклов, в частности, предполагающий отсутствие петель и кратных ребер, именуют деревом. Несвязный неориентированный граф без цикла — лес, его связные компоненты являются деревьями.

Всякая часть леса или дерева есть лес или дерево. Все цепи в подобном графе просты.

Дерево и лес (граф) обозначены на рис. 38.10 и 38.11, соответственно.

38.3_html_16c42f4f.gif
Рис. 38. 10

38.3_html_1c74717d.gif
38.3_html_m5ca1a6c9.gif
Рис. 38. 11

 

Т: Любые две вершины дерева имеют взаимосвязь, обеспечиваемую только одной цепью.

О: Остов графа38.3_html_m11de5e45.gifесть дерево38.3_html_4acedaba.gif

Решение задач оптимизации на графах находится посредством составления оптимального дерева. Разберем одну из задач.

Задача. Определены расстояния между каждой парой из38.3_html_6efbf575.gifвершин. Вершины требуется соединить таким образом, чтобы в результате был представлен неориентированный граф, т.е. дерево с наименьшей общей длиной ветвей, так называемый кратчайший остов.

Обозначим алгоритм построения этого кратчайшего остова. Для начала необходимо построить ребро, которое соединяло бы две вершины с минимальным расстоянием между друг другом. Одна из вершин есть корень дерева, вторая вершина имеет соединение со следующей вершиной, которая выбирается таким образом, чтобы расстояние до любой другой точки из оставшихся вершин было больше расстояния между ними.

Далее осуществляется построение следующих ребер.

Причем пропускают построение ребер, составляющих циклы с ранее построенными. В результате имеем дерево с38.3_html_m719d3084.gifребрами и определенными вершинами. Общая длина ребер такого дерева является минимальной.

Правило актуально для мультиграфа38.3_html_105c475f.gif, по отношению к каждому ребру38.3_html_m505aa2d2.gifкоторого задана мера38.3_html_m10ddc5d0.gif

Для мультиграфа на рис. 38.12 с ребрами и их мерами:

 

38.3_html_m505aa2d2.gif

38.3_html_m507e6adc.gif

38.3_html_34a45765.gif

38.3_html_23b65f8a.gif

38.3_html_1c05a044.gif

38.3_html_5d717267.gif

38.3_html_5e326583.gif

38.3_html_5011b3bc.gif

38.3_html_73abeec.gif

38.3_html_m34a63210.gif

38.3_html_4ac32488.gif

38.3_html_m34a63210.gif

38.3_html_m11104929.gif

38.3_html_162f7fd4.gif

 

38.3_html_40c684a0.gifили38.3_html_mdfc381d.gifможно определить в качестве кратчайшего остова.

Для некоторых здач полезно использование двудольных графов.

О: Граф38.3_html_105c475f.gifименуют двудольным в случае, когда38.3_html_m3062925b.gif, при этом для каждого ребра графа характерно наличие одного конца из38.3_html_m2561863b.gif, другого — из38.3_html_47608631.gif

Использование двудольных графов актуально тогда, когда исследуемые объекты делятся на две группы таким образом, что внутри групп нет изучаемых взаимодействий. Так, для генетики — это признаки и гены, для химии — кислоты и основания, для экономики — производители и потребители.

38.3_html_6ec800de.gif
Рис. 38. 12

 

На рис. 38.13 обозначен пример двудольного графа. Вершины этого графа на диаграмме, как правило, размещают на параллельных прямых.

38.3_html_m7ebe6896_show.gif
Рис. 38. 13

 

 

К двудольным графам имеет отношение задача о назначениях. Предположим, что38.3_html_m2561863b.gifесть множество претендентов на рабочие места, 38.3_html_m36d618d.gifявляется множеством рабочих мест. Требуется всем кандидатам предоставить работу с учетом их профессиональной квалификации.

Допустим, что38.3_html_m51914d50.gif, им соответствует двудольный граф38.3_html_43586c52.gif, обозначенный на рис. 38.14.

38.3_html_36a83278.gif
Рис. 38. 14

38.3_html_749e771e.gif
Рис. 38. 15

 

Сущность задачи заключается в том, чтобы на основе данного графа обозначить подграф38.3_html_m632d2309.gif, который предполагает наличие компонент с двумя вершинами, в качестве соединения которых выступает ребро (рис. 38.15);38.3_html_m632d2309.gifесть подграф назначений.



(38.4.) Сформулируем понятие конечного автомата, обозначим входной алфавит, выходной алфавит, алфавит состояний, функцию переходов, функцию выходов, на рисунке изобразим граф переходов.
2463 0
(38.2.) В рамках обозначенной темы рассмотрим случай определения связного неориентированного мультиграфа в качестве эйлерова и гамильтонова графа.
8987 0
(38.1.) Одним из базовых разделов дискретной математики можно назвать теорию графов. Их применяют при решении задач теории автоматического управления. Применение их актуально и в таких науках, где существуют системы с большим количеством объектов, которые предполагают взаимосвязь, определяемую разнообразными отношениями.
4862 0

    Вы должны авторизоваться, чтобы оставлять комментарии.

    Радиомастер
    © 2005–2013 radiomaster.ru
    admin@radiomaster.ru
    При использовании материалов данного сайта прямая и явная ссылка на сайт radiomaster.ru обязательна. 0.6493 s