Medis (grafų teorija)

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

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

Grafų teorijoje medis – jungus neorientuotas grafas, kuriame kiekviena briauna yra tiltas. Miškas – grafas, kuriame tarp bet kurių viršūnių egzistuoja daugiausiai vienas kelias.

Jungaus grafo Karkasas

tai toks medis, kurio viršūnių aibė sutampa su jungaus grafo viršūnių aibe.

[taisyti] Savybės

• Medis – jungus grafas (tarp bet kurių viršūnių egzistuoja kelias). Iš viso N medyje briaunų yra N -1.
• Jei grafas yra medis, jame nėra ciklų.
• Jei iš medžio pašalinti bet kurią briauną, gausime nejungų (nerišlų) grafą.
• Jei prie medžio pridėti briauną, gausime grafą su paprastu ciklu.
• N Medžio viršūnių laipsnių suma lygi 2 *(N -1)

A. Cayley teorema (1889 m.)

Skirtingų medžių, jungiančių N viršūnes yra N^{N − 2}