Каждой хордовой диаграмме можно поставить в соответствие ее граф пересечений,
множество вершин которого соответствует хордам диаграммы, а ребра -- зацепленности хорд.
Возникает вопрос: для каждого ли простого графа существует хордовая диаграмма,
граф пересечений которой изоморфен исходному графу? Ответ на этот вопрос отрицателен.
В начале 90-х годов А.Буше доказал критерий реализуемости графа в виде хордовой диаграммы.
Критерий формулируется в духе критерия Куратовского-Понтрягина о вложимости графа в плоскость.
В докладе будет разобрано подробно доказательство теоремы Буше о реализуемости графа.
|