Значение различных типов графиков

Question

Существует много named graph types. Мне интересно, каковы критерии этой категоризации. Являются ли разные типы применимыми в разных контекстах? Более того, может ли бизнес-приложение (с точки зрения проектирования и программирования) извлечь выгоду из этой категоризации? Является ли это аналогичным шаблонам проектирования?

Answer 1

Мы дали имена общих семейств графов по нескольким причинам:

• Некоторые семьи графов имеют хорошие, простые свойства. Например, trees имеют множество полезных свойств (между любыми парами узлов есть ровно один путь, они максимально ацикличны, они минимально связаны и т. Д.), Которые не имеют произвольных графов. Directed acyclic graphs может быть topologically sorted, что нормальные графики не могут. Если вы можете моделировать проблему с точки зрения одного из этих типов графиков, вы можете использовать специализированные алгоритмы для их извлечения свойств, которые не обязательно могут быть получены из произвольного графика.

• Некоторые алгоритмы работают быстрее на определенных типах графиков. Многие NP-жесткие проблемы на графиках, которые на данный момент не имеют алгоритмов полиномиального времени, могут быть легко решены на некоторых типах графиков. Например, maximum independent set problem (выберите самую большую коллекцию узлов, где ни один из двух узлов не связан ребрами) NP-жесткий, но может быть разрешен в полиномиальное время для деревьев и bipartite graphs. Проблема с четырьмя цветами (определение того, могут ли узлы графа окрашиваться в один из четырех разных цветов, не присваивая один и тот же цвет соседним узлам) является NP-трудным в общем случае, но это немедленно верно для planar graphs (это знаменитый четыре -цветная теорема).

• Некоторые алгоритмы упрощены для некоторых типов графиков. A matching в графе представляет собой набор ребер в графе, где два ребра не разделяют конечную точку. Максимальные соответствия могут использоваться для представления способов объединения людей в группы. В двудольном графе максимальное совпадение может использоваться для представления способа назначения людей задачам таким образом, чтобы ни одному человеку не было назначено две задачи, и двум задачам не назначена задача. Существует много быстрых алгоритмов для поиска максимальных совпадений в двудольных графах, которые работают быстро и легко понятны. Соответствующие алгоритмы для общих графиков значительно сложнее и немного менее эффективны.

• Определенные графики исторически значимы. Многие названные графы названы в честь тех, кто использовал граф, чтобы опровергнуть гипотезу о свойствах произвольных графов. Например, Petersen graph является контрпримером для многих теорем, которые кажутся правильными относительно графов, но на самом деле их нет.

• Некоторые графики полезны в теоретическом информатике. expander graph - это график, в котором интуитивно любая коллекция узлов должна быть подключена к пропорционально большему набору узлов в графе. Не все графики являются графами расширения. Графики расширений используются во многих результатах теоретической информатики, таких как одно доказательство теоремы PCP и доказательство того, что SL = L.

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

Надеюсь, это поможет!