Связный граф

Cтраница 3

Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро; такая цепь называется эйлеровой цепью. Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. [31]

Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет четную степень. [32]

Неэйлеров ( а и эйлеров ( б графы. [33]

Связный граф G ( X, U) называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро только один раз. [34]

Связный граф G называется А-угольно-критическим, если в нем нет совершенных 2-паросочетаний, не содержащих А - угольников, но для каждой вершины v 6 V ( G) граф G - v имеет совершенное 2-паросочетание, не содержащее А - угольников. Очевидно, что Z - угольно-критические графы являются факторно-критическими. Одновершинный граф есть 0-угольно-критический и других 0-уголь-но - критических графов не существует. [35]

Связный граф G является - угольно-критическим в том и только том случае, когда каждый блок в G является треугольником. [36]

Пусть связный граф О имеет гамильтонов бонд Н с торцевыми графами X и У. [37]

Пусть связный граф О имеет 1-разделение ( Н К) с точкой сочленения V, и пусть Н и К - планарные графы. Тогда граф С планарен. [38]

Неориентированный связный граф без циклов называется деревом. [39]

Рассмотрим связный граф О, не являющийся простым циклом нечетной длины. [40]

Если связный граф не является уникурсальным ( и, следовательно, имеет, по крайней мере, четыре вершины нечетной степени), то доказать, что он имеет, по крайней мере, два различных минимальных реберных разделения. [41]

Каждый связный граф, не содержащий клешней и имеющий четное число вершин, обладает совершенным паросочета-нием. [42]

Рассмотрим конечный связный граф на плоскости, ребра которого не пересекаются вне вершин и в каждой вершине сходятся не менее двух ребер. Доказать, что ограниченная им внутренняя область разбивается на nt - п0 1 попарно не пересекающихся многоугольников. [43]

Если связный граф G имеет в точности одно совершенное паросочетание, то он имеет разрезающее ребро, принадлежащее совершенному паросочетанию. [44]

Деревом называется связный граф без циклов. [45]

Страницы: 1 2 3 4