1. Kas yra medis ir miškas?

Medis

• Grafų teorijoje a medis yra neorientuotas, sujungtas ir aciklinis grafikas . Kitaip tariant, sujungtas grafikas, kuriame nėra nė vieno ciklo, vadinamas medžiu.
• Medis vaizduoja hierarchinę struktūrą grafine forma.
• Medžių elementai vadinami jų mazgais, o medžio kraštai – šakomis.
• Medis su n viršūnių turi (n-1) briaunas.
• Medžiai teikia daug naudingų programų, nuo paprastų kaip šeimos medis iki tokių sudėtingų kaip medžiai kompiuterių mokslo duomenų struktūrose.
• A lapelis medyje yra 1 laipsnio viršūnė arba bet kuri viršūnė, neturinti vaikų, vadinama lapu.

Pavyzdys

Aukščiau pateiktame pavyzdyje visi medžiai turi mažiau nei 6 viršūnes.

Miškas

Grafų teorijoje a miškas yra nenukreiptas, atjungtas, aciklinis grafikas . Kitaip tariant, atskira medžių kolekcija yra žinoma kaip miškas. Kiekvienas miško komponentas yra medis.

skaičiuoti atskirą sql

Pavyzdys

Aukščiau pateikta diagrama atrodo kaip du pografai, tačiau tai yra vienas atskirtas grafikas. Aukščiau pateiktoje diagramoje nėra ciklų. Todėl tai miškas.

2. Medžių savybės

1. Kiekvienas medis, turintis bent dvi viršūnes, turi turėti bent du lapus.
2. Medžiai turi daug savybių:
   Tegul T yra grafikas su n viršūnių, tada šie teiginiai yra lygiaverčiai:
   • T yra medis.
   • T neturi ciklų ir turi n-1 briaunas.
   • T yra sujungtas ir turi (n -1) briauną.
   • T yra sujungtas grafikas, o kiekviena briauna yra pjūvis.
   • Bet kurios dvi grafo T viršūnės yra sujungtos tiksliai vienu keliu.
   • T neturi ciklų, o bet kuriai naujai briaunai e grafikas T+ e turi tiksliai vieną ciklą.
3. Kiekvienas medžio kraštas yra nupjautas.
4. Vienos briaunos pridėjimas prie medžio apibrėžia tiksliai vieną ciklą.
5. Kiekviename sujungtame grafe yra apimantis medis.
6. Kiekvienas medis turi bent dvi antrojo laipsnio viršūnes.

3. Apsauginis medis

A besitęsiantis medis sujungtame grafe G yra G pografas H, kuris apima visas G viršūnes ir yra medis.

Pavyzdys

Apsvarstykite šį grafiką G:

Iš aukščiau pateikto grafiko G galime įgyvendinti šiuos tris apimančius medžius H:

Metodai, kaip rasti besitęsiantį medį

Mes galime sistemingai rasti besitęsiantį medį naudodami vieną iš dviejų būdų:

1. Pjovimo metodas
2. Konstravimo metodas

1. Pjovimo būdas

• Pradėkite pasirinkti bet kurį ciklą G diagramoje.
• Nuimkite vieną iš ciklo kraštų.
• Kartokite šį procesą, kol neliks ciklų.

Pavyzdys

• Apsvarstykite grafiką G,

• Jei pašalinsime kraštą ac, kuris sunaikina ciklą a-d-c-a aukščiau pateiktame grafike, gausime tokį grafiką:

• Pašalinkite kraštą cb, kuris sunaikina ciklą a-d-c-b-a iš aukščiau pateikto grafiko, tada gauname tokį grafiką:

• Jei pašalinsime kraštinę ec, kuri sunaikina ciklą d-e-c-d iš aukščiau pateikto grafiko, gausime tokį apimantį medį:

2. Konstravimo būdas

• Pažymėkite grafo G kraštus po vieną. Sukuriami taip, kad nebūtų ciklų.
• Kartokite šį procesą, kol bus įtrauktos visos viršūnės.

Pavyzdys

Apsvarstykite šį grafiką G,

• Pasirinkite kraštą ab ,

• Pasirinkite kraštą apie ,

• Po to pasirinkite kraštą ec ,

• Tada pasirinkite kraštą cb , tada galiausiai gauname tokį besitęsiantį medį:

Grandinės rangas

Kraštinių skaičius, kurį turime ištrinti iš G, kad gautume tęstinį medį.

Tvirtinimo medis G = m- (n-1) , kuris vadinamas grandinės rangas iš G.

 Where, m = No. of edges. n = No. of vertices. 

Pavyzdys

Aukščiau pateiktame grafike briaunos m = 7, o viršūnės n = 5

Tada grandinės rangas yra

 G = m - (n - 1) = 7 - (5 - 1) = 3