En spændende undergraf er en undergraf, der indeholder alle hjørnerne af den originale graf. Et spændingstræ er en spændende undergraf, der ofte er af interesse. En cyklus i en graf, der indeholder alle toppunkterne i grafen, vil blive kaldt en spændingscyklus.
Hvor mange spændende undergrafer er der?
Der er 2n inducerede subgrafer (alle delmængder af toppunkter) og 2m spændende undergrafer (alle delmængder af kanter).
Hvordan finder jeg en spændende undergraf?
Og per definition af spændvidde undergraf i en graf er G en undergraf kun opnået ved kantsletning. Hvis vi laver delmængder af kanter ved at slette en kant, to kant, tre kant og så videre. Da der er m kanter, så er der 2^m delmængder. Derfor har G 2^m spændende undergrafer.
Hvad menes med spanning tree?
Det spændende træ i en graf (G) er en delmængde af G, der dækker alle dets hjørner ved at bruge det mindste antal kanter. Nogle egenskaber ved et spændingstræ kan udledes af denne definition: Da "et spændingstræ dækker alle hjørnerne", kan det ikke afbrydes.
Hvad er spændingsgrafteori?
Et spændingstræ er en delmængde af graf G, som har alle toppunkter dækket med mindst muligt antal kanter. Derfor har et spændingstræ ikke cyklusser, og det kan ikke afbrydes. Ved denne definition kan vi drage en konklusion om, at hver forbundne og urettede graf G har mindst ét spændingstræ.
