Двусвязный граф

Cтраница 1

Двусвязный граф О не планарен тогда и только тогда, когда он имеет подграф Н, в котором есть такой цикл С, что для Н граф С-мостов не является двудольным. [1]

Двусвязный граф, содержащий не менее двух ребер, петель не имеет. Трехсвязньш граф, содержащий не менее четырех ребер, является простым графом. [2]

Пусть двусвязный граф О является объединением двух, реберно непересекающихся подграфов Н и К, имеющих ровно две общие вершины Ь и с. Пусть каждый из подграфов Н и К содержит хотя бы одно ребро. [3]

Если двусвязный граф В, отличен от графа-звена и не содержит петель, то в нем должно быть хотя бы два ребра. Он является тогда вторым членом 2-разделения ( Я, В) графа С и при этом ребро А принадлежит Я. Условия ( I) и ( 11) определения Л - мажорантности, очевидно, выполняются, и мы можем рассматривать совокупность ( Я, В) 2-разделений графа О как совокупность Л - мажорантных 2-разделений. [4]

Теорема 111.15. Двусвязный граф имеет в точности один блок - это сам рассматриваемый граф. Разделимый граф содержит не менее двух блоков. [5]

Два 1-фактора блока. [6]

Теорема 9.3. Если двусвязный граф имеет - фактор, то он имеет по крайней мере два различных 1-фактора. [7]

Если G - двусвязный граф, то каждая его вершина соответствует коциклу ( минимальному разрезу), содержащему инцидентные ей ребра. Поэтому матрица инциденций блока содержится в его матрице коциклов. [8]

Пусть О - любой двусвязный граф, не являющийся графом-вершиной, графом-звеном или циклом. Тогда либо О есть тэта-граф, либо в нем найдется такой цикл С, что в О будет по меньшей мере два С-моста. [9]

Теорема 111.6. Пусть О - двусвязный граф и Я - непустой его подграф, не являющийся графом-вершиной. Если В является Н - мостом в графе О, то в Н содержатся хотя бы две вершины из В. [10]

Теорема 111.11. Пусть О - двусвязный граф, содержащий хотя бы два ребра. [11]

Я, мы всегда получаем двусвязный граф. Кроме того, из теоремы 111.11 следует, что каждый двусвязный граф, содержащий хотя бы два ребра, может быть построен указанным присоединением цепи к некоторому подходящему меньшему двусвязному графу. [12]

Теорема 111.30. Пусть О - двусвязный граф, содержащий хотя бы два ребра, и А - некоторое ребро этого графа. Тогда подграф О А либо является двусязным, либо представляет собой нить блоков, из которой граф С получается путем замыкания ее ребром А. [13]

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

Теорема 7.2. Каждый гамилыпонов граф двусвязен. Каждый негамильтонов двусвязный граф содержит тэта-подграф. [15]

Страницы: 1 2