Велика енциклопедия на нефт и газ

Двойно свързана графика

Двойно свързаната графика O не е плоска, ако и само ако има подграф H, в който има цикъл C, такъв, че за H графата C-bridge не е двустранна. [един]

Двойно свързана графика, съдържаща поне два ръба, няма цикли. Три свързана графика, съдържаща поне четири ръба, е проста графика. [2]

Нека двойно свързана графика O е обединението на два неграмотни подграфа H и K, имащи точно два общи върха b и c. Нека всяка от подграфите H и K съдържа поне един ръб. [3]

Ако двойно свързана графика B се различава от графика на връзката и не съдържа цикли, тогава тя трябва да има поне два ръба. Тогава той е вторият член на 2-разделянето (R, B) на графика C, а ръбът A принадлежи на H. Условията (I) и (11) от дефиницията на A-мажоранта очевидно са изпълнени и ние може да разгледа колекцията (R, B) 2-дяла на графика O като набор от A - мажорантни 2-дяла. [4]

Теорема 111.15. Двойно свързаната графика има точно един блок - това е самата графика. Делимата графика съдържа поне два блока. [пет]

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

Ако G е двойно свързан граф, тогава всеки от неговите върхове съответства на коцикъл (минимален разрез), съдържащ ръбовете, падащи към него. Следователно матрицата на честотата на даден блок се съдържа в неговата матрица на коцикли. [8]

Нека O е всяка двойно свързана графика, която не е върхова графика, графика на връзката или цикъл. Тогава или O е тета-графика, или съдържа такъв цикъл C, че O съдържа поне два C-моста. [девет]

Теорема 111.6. Нека O е двойно свързан граф, а Я - непразният му подграф, който не е граф на върха. Ако B е H - мост в графика O, тогава H съдържа поне два върха от B. [10]

Теорема 111.11. Нека O е двойно свързана графика, съдържаща поне два ръба. [единадесет]

Аз, винаги получаваме двойно свързана графика. Освен това от теорема 111.11 следва, че всеки двойно свързан граф, съдържащ поне два ръба, може да бъде конструиран чрез посоченото присъединяване на верига към някакъв подходящ по-малък двойно свързан граф. [12]

Теорема 111.30. Нека O е двойно свързан граф, съдържащ поне два ръба, а A - някакъв ръб на тази графика. Тогава подграфът OA е или двуезичен, или е нишка от блокове, от които се получава графиката C, като се затвори с ръб А. [13]

Използвайки доказаните от нас теореми, можем да изградим алгоритъм, който дава възможност да се установи дали даден двойно свързан граф O. е равен. Първо, проверяваме дали O е граф на връх, графика на връзката, цикъл или тета графика. [14]

Теорема 7.2. Всяка графика на Hamilipon е двойно свързана. Всяка нехамилтонова двойно свързана графика съдържа тета подграф. [петнадесет]