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