Модульный граф
В теории графов , разделе математики, модульные графы — это неориентированные графы , в которых каждые три вершины x , y и z имеют хотя бы одну медианную вершину m ( x , y , z ) , которая принадлежит кратчайшим путям между каждой парой x. , у и z . [1] Их название происходит от того факта, что конечная решетка является модулярной решеткой тогда и только тогда, когда ее диаграмма Хассе является модулярным графом. [2]
Модульный граф не может содержать цикл нечетной длины. Ибо, если C — кратчайший нечетный цикл в графе, x — вершина C , а yz — ребро C, наиболее удаленное от x , не может быть медианы m ( x , y , z ) . В этом случае единственными вершинами на кратчайшем пути yz являются сами y и z . Ни один из них не может принадлежать кратчайшему пути от x к другому без сокращения C и создания более короткого нечетного цикла. Поскольку у них нет нечетных циклов, каждый модульный граф является двудольным . [1]
Модульные графы содержат в качестве частного случая медианные графы , в которых каждая тройка вершин имеет уникальную медиану; [1] Медианные графы связаны с дистрибутивными решетками так же, как модульные графы связаны с модульными решетками. Однако модульные графы также включают в себя другие графы, такие как полные двудольные графы , в которых медианы не уникальны: когда все три вершины x , y и z принадлежат одной стороне двудольного графа, каждая вершина на другая сторона является медианой. [2] Каждый хордальный двудольный граф (класс графов, который включает полные двудольные графы и двудольные дистанционно-наследственные графы ) является модулярным. [1]
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б с д Модульные графы , Информационная система по классам графов и их включениям, получено 30 сентября 2016 г.
- ↑ Перейти обратно: Перейти обратно: а б Бандельт, Х.-Ю.; Дельманн, А.; Шютте, Х. (1987), «Абсолютные ретракты двудольных графов», Discrete Applied Mathematics , 16 (3): 191–215, doi : 10.1016/0166-218X(87)90058-8 , MR 0878021 .