Шнитграф ⇐ Васина Википедия

[wiki_de]

В теории графов «граф пересечений» — это граф (теория графов)|граф, который представляет пересечения|разрезы семейства множеств (математика)|множеств как ребра. Каждый набор соответствует узлу графа пересечений. Для каждой пары двух пересекающихся множеств в семействе граф пересечений имеет ребро; и наоборот, между двумя непересекающимися множествами не существует ребра.

== Формальное определение ==
Формально граф пересечений G — это граф (теория графов)|неориентированный граф семейства множеств

: S_i, \,\,\, i = 0, 1, 2, \dots

представляет, представляя каждый набор S_i посредством узла v_i, а два узла v_i и v_j точно соединены тогда , если множества, которые они представляют, образуют пустое множество|непустой разрез, т.е.

: E(G) = \{ \{ v_i, v_j \} \mid i \neq j, S_i \cap S_j \neq \empty \}.

== Литература ==

*
== Дальнейшее чтение ==

* Обзор теории графов пересечений можно найти в McKee & McMorris (1999).

Макки, Терри А.; МакМоррис, Ф.Р. (1999), Темы теории пересекающихся графов, Монографии SIAM по дискретной математике и приложениям, том. 2, Филадельфия: Общество промышленной и прикладной математики, ISBN 0-89871-430-3, MR 1672910.

== Внешние ссылки ==

* Ян Краточвил, [http://videolectures.net/sicgt07_kratochvil_gig/ Видеолекция по графам пересечений (июнь 2007 г.)]
* Э. Приснер, [http://www.eprisner.de/Journey/Rahmen.html Путешествие через графство пересечений]
Категория:Теория графов

Подробнее: https://de.wikipedia.org/wiki/Schnittgraph