Medis (grafų teorija)

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką
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 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.

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

Savybės[taisyti | redaguoti kodą]

  • 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 N^{N-2}.


Commons-logo.svg Vikiteka: Medis (grafų teorija) – vaizdinė ir garsinė medžiaga

Vikiteka