Модулярные графы — это неориентированные графы, в которых любые три вершины , и имеют по меньшей мере одну медианную вершину , которая принадлежит кратчайшим путям между каждой парой , и Modular graphs , Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.. Название происходит из факта, что конечная решётка является модулярной тогда и только тогда, когда её диаграмма Хассе является модулярным графом.
Модулярные графы не могут содержать циклы нечётной длины. Если таковой есть и является самым коротким таким циклом в графе, является вершиной в , а пара вершин образуют наиболее удалённое от ребро цикла, то медианы не существует — кратчайшим путём между вершинами и будет ребро , но ни одна из этих вершин не может лежать на кратчайшем пути из другой в так, чтобы не «срезать путь» по диагонали цикла. Но если у цикла нечётной длины есть диагональ, то она разбивает его на два цикла меньшей длины, одна из которых нечётная, что противоречит тому, что — самый короткий цикл нечётной длины. Поэтому любой модулярный граф является двудольным графом.
Частным случаем модулярных графов являются медианные графы, в которых каждая тройка вершин имеет единственную медиану. Медианные графы связаны с в том же смысле, в котором модулярные графы связаны с модулярными решётками. Однако не все модулярные графы являются медианными — в полных двудольных графах медианы не уникальны, так как для трёх вершин , и из одной доли полного двудольного графа любая вершина другой доли является медианой. Любой хордальный двудольный граф (класс графов, который включает полные двудольные графы и двудольные дистанционно-наследуемые графы) является модулярным.
Примечания
Литература
Категория:Семейства графов Категория:Двудольные графы