Выпуклый двудольный граф

В математической области теории графов выпуклый двудольный граф — это двудольный граф с определенными свойствами.Двудольный граф ( U ∪ V , E ) называется выпуклым над множеством вершин U, если U можно пронумеровать так, что для всех v ∈ V вершины, смежные с v, являются последовательными.

Выпуклость над V определяется аналогично. Двудольный граф ( U ∪ V , E ), выпуклый как над U , так и над V, называется двояковыпуклым или двояковыпуклым .

Формальное определение

Пусть G = ( U ∪ V , E ) — двудольный граф, т. е. множество вершин — это U ∪ V , где U ∩ V = ∅. Обозначим через NG _V. ( v окрестность v ∈ ) вершины Граф G является выпуклым над U тогда и только тогда, когда существует биективное отображение f : U → {1, …, | U |}, такой, что для всех v ∈ V ,для любых двух вершин x , y ∈ NG _f ( v ) ⊆ U не существует z ∉ N _G ( v ) такого, что ( x ) < f ( z ) < f ( y ).

См. также

• Выпуклый плоский граф

Ссылки

• В. Липски-младший; Франко П. Препарата (август 1981 г.). «Эффективные алгоритмы поиска максимальных паросочетаний в выпуклых двудольных графах и связанные с ними проблемы». Акта Информатика . 15 (4): 329–346. дои : 10.1007/BF00264533 . hdl : 2142/74215 . S2CID   39361123 .
• Тен-хван Лай; Шу-шан Вэй (апрель 1997 г.). «Двудольные графы перестановок с применением к проблеме минимального размера буфера» . Дискретная прикладная математика . 74 (1): 33–55. дои : 10.1016/S0166-218X(96)00014-5 . Проверено 20 июля 2009 г.
• Джереми П. Спинрад (2003). Эффективные представления графов . Книжный магазин АМС . п. 128. ИСБН  978-0-8218-2815-1 . Проверено 20 июля 2009 г.
• Андреас Брандштедт ; Ван Банг Ле; Джереми П. Спинрад (1999). Классы графов: опрос . СИАМ . п. 94 . ISBN  978-0-89871-432-6 . Проверено 20 июля 2009 г. выпуклый, если есть упорядочение.