Diskusia s redaktorom:Patrick23

Ahoj, Patrick23. Vítame Ťa v slovenskej Wikipédii! / Welcome to the Slovak Wikipedia!
Slovenská Wikipédia je slovenská jazyková verzia Wikipédie, ktorá vznikla v októbri 2003 a k dnešnému dňu má 248 663 článkov. Začal(a) si dobre a si na najlepšej ceste začať prispievať a pridávať množstvo dobrých článkov. Ďakujeme za Tvoj prínos k tvorbe encyklopédie a tešíme sa na spoluprácu. Veríme, že sa nám bude dobre spolu pracovať a že sa tu budeš medzi ostatnými cítiť príjemne. Odporúčame Ti, aby si si prečítal/a nasledujúce stránky, ktoré Ti uľahčia prácu pri Tvojom upravovaní:
	Príručka		Pieskovisko (miesto pre experimenty)
	Obsah Pomocníka		Kaviareň (diskusia redaktorov)
	Často kladené otázky		Päť pilierov Wikipédie
	Wikitext		Čo Wikipédia nie je
Na diskusných stránkach sa vždy podpisuj: stačí napísať 4 vlnovky ~~~~ alebo ich vložiť kliknutím na ikonu v lište nad oknom na úpravu. Naopak články sa nikdy nepodpisujú.
Tak ešte raz vitaj a ďakujeme za Tvoje príspevky. Dúfame, že sa tu uvidíme často. Za uvítací výbor: Marián_2 If you have questions, comments, or something is not clear to you, or if you would like to know something about the Slovak Wikipedia, look at the Slovak Wikiembassy, where someone might even help you in your language :).

Hamiltonovské grafy

Úvod

V roku 1857 WILLIAM R. HAMILTON zostrojil matematický hlavolam, ktorého cielom bolo nájst takú uzavretú prechádzku po hranách pravidelného dvanáststena, ktorá by obsahovala každý vrchol práve raz. Ak zabudneme na plochy dvanáststena a nakreslíme jeho vrcholy a hrany v rovine, tak dostaneme graf nakreslený na obrázku:

Definícia Hamiltonovskej kružnice

Hamiltonovská kružnice grafu je taká cesta, ktorá prejde práve raz všetky vrcholy grafu a medzi jeho začiatočným a konečným vrcholom existuje platná cesta. Teda riešením Hamiltonovho hlavolamu je Hamiltonovská kružnica. Zistiť, či má graf uzavretý Eulerovský ťah, je ľahký problém, lebo stačí zistiť súvislosť grafu a paritu stupňov všetkých jeho vrcholov. Je prekvapujúce, že analogický problém pre Hamiltonovské kružnice je ťažký. Tento problém patrí do skupiny takzvaných NP-úplných problémov. Poznáme však veľmi veľa podmienok, ktorých splnenie vynucuje v grafe existenciu Hamiltonovskej kružnice. Jednu z najznámejších postačujúcich podmienok tohto typu dokázal O. ORE v roku 1960(1.podmienka).

Postačujúce podmienky

1. Nech G je graf, |V | = n, n ≥ 3. Ak pre každú dvojicu vrcholov, ktoré nie sú spojené hranou súčet ich stupňov je aspoň n, tak G je hamiltonovský.

2. Nech G je graf, |V | = n, n ≥ 3. Ak má každý vrchol stupeň aspoň n/2 , tak graf je hamiltonovský.

3. Nech G je graf, |V | = n a predpokladajme, že n ≥ 3. Ak pre každé prirodzené číslo k < n/2 je počet vrcholov, ktorých stupeň neprevyšuje k, menší ako k, tak je graf hamiltonovský.

Príklady

Uvedieme si príklady, kedy je graf hamiltonovsky a kedy graf nie je.

1.Príklad

                                       
               Obr.1                                                       Obr.2

Podľa podmienok uvedených hore graf ktorý je uvedený hore na obrázku(Obr. 1) nie je Hamiltonovský, pretože nespĺňa ani jednu z podmienok. Síce nespĺňa ani jednu z podmienok ale dá sa nakresliť hamiltonovská kružnica, ktorú som uviedol červenou farbou na obr. 2. Je to možno spôsobené tým, že neexistuje nutná podmienka hamiltonovskych grafov.

2.Príklad

Graf na obrázku spĺňa všetky 3 podmienky: 1. podmienku, lebo každý jeho vrchol má stupeň aspoň 3 a spĺňa aj 2. podmienku, lebo každé dva vrcholy nespojené hranou majú súčet stupňov aspoň 6. A konečne spĺňa aj 3. podmienku, lebo v ňom nie sú žiadne vrcholy stupňa menšieho ako 3.