В теории графов , разделе математики, модульные графы представляют собой неориентированные графы, в которых каждые три вершины x , y и z имеют по крайней мере одну срединную вершину m ( x , y , z ), которая принадлежит кратчайшим путям между каждой парой x , y и z . [1] Их название происходит от того факта, что конечная решетка является модульной решеткой тогда и только тогда, когда ее диаграмма Хассеявляется модульным графом. [2]
Модульный граф не может содержать цикл нечетной длины. Ибо, если C - кратчайший нечетный цикл в графе, x - вершина C , а yz - край цикла, наиболее удаленный от x , не может быть медианы m ( x , y , z ) для единственных вершин на кратчайшем пути yz находятся сами y и z , но ни один из них не может принадлежать кратчайшему пути от x до другого без сокращения C и создания более короткого нечетного цикла. Следовательно, каждый модульный граф являетсядвудольный граф . [1]
Модульные графы содержат как частный случай медианные графы , в которых каждая тройка вершин имеет уникальную медиану; [1] медианные графы связаны с дистрибутивными решетками так же, как модульные графы связаны с модульными решетками. Однако модульные графы также включают в себя другие графы, такие как полные двудольные графы, в которых медианы не уникальны: когда все три вершины x , y и z принадлежат одной стороне двудольного графа полного двудольного графа, каждая вершина на другая сторона - медиана. [2] Каждый хордовый двудольный граф(класс графов, который включает полные двудольные графы и двудольные графы с дистанционной наследственностью ) является модульным. [1]
Ссылки [ править ]
- ^ a b c d Модульные графы , Информационная система по классам графов и их включениям, получено 30 сентября 2016 г.
- ^ a b Bandelt, H.-J .; Dählmann, A .; Шютте, Х. (1987), «Абсолютные ретракты двудольных графов», Дискретная прикладная математика , 16 (3): 191–215, DOI : 10.1016 / 0166-218X (87) 90058-8 , MR 0878021.
