Modular graph

rdf:langString Модулярный граф

rdf:langString Модулярные графы — это неориентированные графы, в которых любые три вершины x, y и z имеют по меньшей мере одну медианную вершину m(x,y,z), которая принадлежит кратчайшим путям между каждой парой x, y и z.Название происходит из факта, что конечная решётка является модулярной тогда и только тогда, когда её диаграмма Хассе является модулярным графом. Модулярные графы не могут содержать циклы нечётной длины. Если таковой есть и C является самым коротким таким циклом в графе, x является вершиной в C, а пара вершин yz образуют наиболее удалённое от x ребро цикла, то медианы m(x,y,z) не существует — кратчайшим путём между вершинами y и z будет ребро yz, но ни одна из этих вершин не может лежать на кратчайшем пути из другой в x так, чтобы не «срезать путь» по диагонали цикла. Но если у цикла нечётной длины есть диагональ, то она разбивает его на два цикла меньшей длины, одна из которых нечётная, что противоречит тому, что C — самый короткий цикл нечётной длины. Поэтому любой модулярный граф является двудольным графом. Частным случаем модулярных графов являются медианные графы, в которых каждая тройка вершин имеет единственную медиану. Медианные графы связаны с в том же смысле, в котором модулярные графы связаны с модулярными решётками. Однако не все модулярные графы являются медианными — в полных двудольных графах медианы не уникальны, так как для трёх вершин x, y и z из одной доли полного двудольного графа любая вершина другой доли является медианой. Любой хордальный двудольный граф (класс графов, который включает полные двудольные графы и двудольные дистанционно-наследуемые графы) является модулярным.