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

Последователност - ребро

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

Като се вземат предвид диафрагмите, съответстващи на фиг. 5.33 (вляво) и 5.34 (вдясно), показват как се посещават възлите в графика, изградена за последователност от ръбове 0 - 2, 1 - 4, 2 - 5, 3 - 6, 0 - 4, 6 - 0 и 1 - 3 (вж. Упражнение 3.70), с рекурсивно търсене на дълбочина първо. [32]

Графика G (X, A) се нарича пълна, ако за всяка двойка върхове има поне един ръб. Последователност от ръбове, в които всеки два съседни ръба са съседни, се нарича графичен маршрут. [33]

Нека въведем още няколко определения, които ще ни трябват при следващото ни разглеждане. Последователност от ребра 1с, в която всеки ръб има един връх, граничещ със следващия ръб, а другият с предишния, се нарича верига, а около графика, в която всеки два върха могат да бъдат свързани чрез верига, казваме че графиката е свързана. [35]

Последователност от ребра, в които началните и крайните върхове съвпадат, се нарича цикъл. Ако последователността от ръбове включва цикли, тя не може да бъде елементарна. [36]

Структурното дърво е обозначена графика (обозначени ръбове и възли), където възлите съответстват на граматически типове или синтактични единици, а ръбовете се отличават с поредния им номер. Дървесната верига е последователност от ръбове, всеки от които е свързан с предишния. В лингвистиката думите или последователностите, които функционират като елементи на друга конструкция, се наричат съставни елементи. [37]

Проблеми от този тип се решават в теорията на графовете, която многократно се споменава в нашата книга. Пътят в графика е последователност от ребра, в които всеки два съседни ръба имат общ връх. [39]

Да предположим, че върховете x и y са свързани от R Lxy чрез система от k l прости пътеки, които нямат други общи върхове по двойки. На всяка такава верига съответства в L последователност от различни ръбове, чиито съседни ръбове са съседни (имат общ падащ връх), а всички k последователности по двойки нямат общи ръбове. [40]

Сега оставяме z и започваме пътя по следващия ръб, излизащ от r. Всеки път, когато преминем край на дървото, продължаваме да изграждаме пътя; когато преминем задния ръб, той става последният ръб на текущия път. По този начин всеки път се състои от поредица от дървесни ръбове (броят им е 0), последван от един заден ръб. Новият път започва от началния връх на последния заден ръб; ако в този връх няма повече неизследвани ръбове, върнете се към предишния връх на последния път. Процесът продължава, докато графиката G свърши с непроменени ръбове. Алгоритъм 8.14 прилага това разлагане на диграфа в път и цикъл. [41]

На фиг. 2.4.2 a, b, e, g - висящи върхове, c, d и f - възли. Очевидно е, че те могат да се разглеждат като част от последователност от ръбове, свързващи други върхове. [42]

Нека графиката Γ няма двойно циклични върхове. Ние наричаме верига подграф на графика Γ, състоящ се от поредица от ребра, в която краят на предишния ръб е началото на следващия и нито един връх не се появява два пъти. [43]

Очевидно е, че времето за работа на процедурата VERTEX (/) е пропорционално на броя на ръбовете, падащи на Vj. По същия начин можете да изградите FACE (/) процедура, която генерира последователност от ръбове, заобикалящи лицето//; за това в описаната по-горе процедура VERTEX (/) масивите HV и 1/1 трябва да бъдат заменени съответно с масивите HF и FI. Имайте предвид, че VERTEX търси ръбове, като се движи обратно на часовниковата стрелка около върха, докато FACE търси ръбове, като се движи по посока на часовниковата стрелка около лице. [44]

Понякога е важно да се прави разлика между различни начини за подреждане на ръбове при оформяне на вериги или бримки, в други случаи подреждането не съществува. И двете ситуации са доста често срещани, така че въвеждането на различни термини за подредени и неподредени последователности от ръбове е напълно оправдано. [45]