Stretcher

Материал из WikiGrapp
Версия от 15:31, 28 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''Stretcher''' --- носилки. A '''stretcher''' is a graph whose edge set may be partitioned into two triangles and three vertex-disjoint chordless paths, ea…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Stretcher --- носилки.

A stretcher is a graph whose edge set may be partitioned into two triangles and three vertex-disjoint chordless paths, each with endpoints in both triangles

In a graph with no odd hole, every induced stretcher has three vertex-disjoint chordless paths of the same parity; therefore, a stretcher is called odd or even depending on the parity of the paths (odd or, respectively, even).