Знайте, Intuit, лекция, някои определения на теория на графите

Свързани графики. в който има един и само един път, свързващ всеки чифт върхове се наричат дървета. Едно дърво може да се дефинира като свързан граф. без цикли.

Пример. Купа на тенис на маса се играе на олимпийския система. Провеждат се срещи, без да "обръща". За следващия кръг разрешено само печеливш екип в предишния кръг. Екипите за губят се елиминират от играта. За да спечели отбора Cup трябва да спечели във всички кръгове. За участие в екипите купа от подадените заявления.

Схемата на игрите описва граф

В горната част на по-ниска "подреждане" на дървото се тълкува като екипите, участващи в турнира за Купата, в началото на втората част от дъното - като отбора победител на финала, в началото на третото ниво - като печеливш екип във финала, и т.н.

Каква информация може да бъде получена с това дърво?

Директно чете от него:

Броят на участниците в турнира за Купата (по-ниска е броят на "нива" на върха).
Броят на етапи на изготвянето (броят на "нива" на възли в едно дърво, без да се броят на дъното).
Броят на отборите, участващи във финала, на финала, слагайки край (броят на върховете, съответно, през четвъртото ниво от върха, на върха в третата част, втората част от горната част).
Броят на мачове, които трябва да играят отборите за идентифициране на собственика на купа (броят на върховете в графика без по-ниска "подреждане"). Въпреки че тази цифра може лесно да се определи без едно дърво. (Във всеки мач, екип, се елиминира. За да се печеливш екип, а останалите трябва да се оттегли от състезанието е бил идентифициран. Следователно, броят на мача е равен на броя на отборите, без един, а именно).

Той е удобен да се предположи, че графиката. състояща се от един изолирани пикове, също дърво. За всяка двойка от върховете на дървото има уникален начин за свързването им. Гора е изключен графика. представлява обединението на дървета. Всеки край на дърво в гората и мост (функция 3).

Тя показва гората. състояща се от четири компонента. всеки от които е дърво.

Имайте предвид, че по дефиниция дървета и гори са прости графики. В много отношения дървото е най-простият nontrivial тип графика.

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

Като цяло, ние означаваме произволна графика с върхове, ръбове и компоненти. Прилагането на по-горе процедура за всеки компонент, ние получаваме в резултат на преброяването. нарича обхваща гора. Броят на отдалечени краища в тази процедура се нарича цикличен или цикличен ранг номер на графика и се означава с. Виждаме, че е неотрицателно число. По този начин, цикличен ранг дава мярка на графиката: циклична ранг дърво е нула и цикличен ранг цикличен графика е единство. Също така е удобно да се определи Cocycle степен или звание графика намали броя на ръбовете в своя обхваща гора. Cocycle ранг е обозначен с ф.

Теорема 2.1 дърво с върховете има ръб.

Доказателство за едно дърво, не е изолиран връх. получите две дървета със същите върховете, трябва да бъдат отстранени от един ръб. За образуването на три дървета да бъдат извадени от всеки две ребра. Най-много от дърво с върховете на дърветата са на разположение, всяка от които е изолиран връх. За да направите това, премахване на края на гората. Така че, наистина, в дървото върховете с - предимство.