A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Podľa názoru niektorých redaktorov by tento článok mal byť spojený s článkom Grafová postupnosť. Ak s tým nesúhlasíte, vyjadrite sa, prosím, v diskusii. |
Tento článok alebo jeho časť si vyžaduje úpravu, aby zodpovedal vyššiemu štandardu kvality. Prosím, pozrite si stránky pomocníka, odporúčanie pre encyklopedický štýl a článok vhodne upravte. |
Grafová postupnosť
V obyčajnom neorientovanom grafe G s vrcholovou množinou môžeme zostrojiť postupnosť nezáporných celých čísel. Takúto postupnosť nazývame stupňová postupnosť. Ak vrcholy budú označené tak, že , túto postupnosť nazveme grafová postupnosť. Pre grafové postupnosti platí užitočná veta:
Veta :Postupnosť nezáporných celých čísel, kde a a je grafová práve vtedy, keď je grafová postupnosť
Túto vetu použijeme aj pri konštrukcii algoritmu na zistenie, či daná postupnosť je grafová.
Algoritmus (na zistenie, či daná postupnosť je grafová)
- Ak postupnosť obsahuje člen prevyšujúci n-1, postupnosť nie je grafová. STOP. Inak pokračuj krokom 2.
- Ak sú všetky členy postupnosti rovné 0, potom postupnosť je grafová. STOP Ak postupnosť obsahuje záporné číslo, potom postupnosť grafová nie je. STOP Inak pokračuj bodom 3.
- Ak je to potrebné, usporiadaj členy postupnosti zostupne. Pokračuj krokom 4.
- Zmaž prvý člen (nazvime ho k) a zníž o jednotku hodnotu nasledujúcich k členov postupnosti. Pokračuj krokom 2.
Príklad : Zistite, či daná stupňová postupnosť je grafová.
Riešenie. Postupnosť je usporiadaná. Označme si neusporiadanú postupnosť, ktorá vznikne v i-tom kroku algoritmu a túto postupnosť po usporiadaní . krok 1. Postupnosť má 7 členov. Prvý člen 4 je menší ako 6 (neprevyšuje 5), pokračujeme bodom 2.
Podľa priebehu algoritmu môžeme zostrojiť obyčajný neorientovaný graf, ktorý bude mať grafovú postupnosť . Začneme poslednou postupnosťou a dostaneme sa až k postupnosti . Postupnosť je tvorená dvoma nulami, to znamená, že k nej prislúchajúci graf tvoria dva izolované vrcholy. (Podľa označenia v4 a v6 ). Z postupnosti sme ju dostali odstránením vrcholu v1 a hrany incidentnej s ním a vrcholom v6. Podobne postupujeme, až kým sa nedostaneme k postupnosti .
Grafovou postupnosťou však graf nie je jednoznačne určený. Grafovú postupnosť 2,2,2,1,1 spĺňajú grafy G1 i G2.
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Binárny strom (teória grafov)
Cesta (teória grafov)
Chromatické číslo
Chromatický index
Cyklomatické číslo grafu
Eulerovský ťah
Excentricita (teória grafov)
Faktor grafu
Farbenie grafu
Farbenie vrcholov
Grafová postupnosť
Graf (matematika)
Hamiltonovská kružnica
Hamiltonovský graf
Hrana (teória grafov)
Komplement grafu
Komponent grafu
Kostra grafu
Kružnica (teória grafov)
Minimálna kostra grafu
Most (teória grafov)
Neplanárny graf
Nezávislá množina
Ohodnotený graf
Oreho veta
Orientované stromy
Párny graf
Petersenov graf
Podgraf
Priesečníkové číslo (teória grafov)
Problém obchodného cestujúceho
Problém siedmich mostov
Rovinný graf
Súvislý graf
Sled (teória grafov)
Spektrálna teória grafov
Strom (teória grafov)
Teória grafov
Teória grafov – grafová postupnosť
Topologická teória grafov
Vrchol (teória grafov)
Vzdialenosť (teória grafov)
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk