Medis (grafų teorija)

Kitos reikšmės – Medis (reikšmės).

Medis

Grafų teorijoje medis – jungus neorientuotas grafas be ciklų. Miškas – grafas, sudarytas iš vieno ar kelių medžių. Šakniniu medžiu vadiname medį, kurio viena viršūnė yra išskirta iš kitų ir vadinama šaknimi. Žymėtu medžiu vadiname medį, kurio visos viršūnės pažymėtos skirtingomis žymėmis (paprastai medžio su N viršūnių viršūnės žymimos žymėmis ${\displaystyle 1,2,\ldots ,N}$).

Jungaus grafo karkasas – medis, kurio viršūnių aibė sutampa su jungaus grafo viršūnių aibe, o briaunų aibė yra jungaus grafo briaunų aibės poaibis.

Terminą „medis“ (angl. tree) 1857 m. sukūrė britų matematikas Arthur Cayle.^[1]

Miško ir medžio palyginimas: kiekviename grafike pavaizduotas miškas, mišką sudaro nuo 1 iki n medžių

Savybės

• Tarp bet kurių dviejų medžio viršūnių egzistuoja vienintelis kelias.
• N viršūnių turintis medis (N-medis) visada turi N -1 briauną.
• Kiekviena medžio briauna yra tiltas, t. y., iš medžio pašalinę tą briauną gauname nejungų (nerišlų) grafą.
• Prie medžio pridėję briauną, gauname grafą su paprastu ciklu.
• N-medžio viršūnių laipsnių suma lygi 2(N -1).

A. Cayley teorema (1889 m.)

Skirtingų žymėtų N-medžių skaičius yra ${\displaystyle N^{N-2}}$.

Šaltiniai

1. „The Historic Roots of Tree Graphs: A. Cayley, 1857“. JF Ptak Science Books // Blog Bookstore. Nuoroda tikrinta 2024-02-02.

Vikiteka: Medis (grafų teorija) – vaizdinė ir garsinė medžiaga