Matematické Fórum

Vygooglit není problém:
http://en.wikipedia.org/wiki/Matching
http://en.wikipedia.org/wiki/Bipartite_graph -- tam je i obrázek grafu s kompl. párováním (tzv. bipartitního grafu)
Jinak u téhle úlohy ten strom zakořeň a zjisti, s jakým vrcholem může sousedit list, který je nejdál od kořene.

↑ Kondr:
ahoj, koukala jsem na ty odkazy a porad se nejak nevim rady. Mohl by mi to nekdo vysvetlit trosku podrobneji co bych mela udelat? Diky moc

Názvosloví beru odtud: http://cs.wikipedia.org/wiki/Strom_(graf)#Zako.C5.99en.C4.9Bn.C3.BD_strom
1) Ve stromě si mohu zvolit jeden vrchol a nazvat ho kořenem
2) Existují vrcholy, které od něj mají maximální vzdálenost
3) Tyto vrcholy jsou listy
4) Jeden z nich označím L1
5) Rodiče vrcholu L1 označím P
6) Potomci vrcholu P jsou L1,L2,...Lk.
7) Mezi žádnými dvěma vrcholy Li, Lj nevede hrana
8) Vrcholy Li nemají žádné potomky
9) Vrcholy Li sousedí pouze s P
10) Párovací hrana z Li vede do P, a to pro všechna i od 1 do k
11) k=1
13) Vrchol P není kořenem, protože má jediného potomka a graf má víc než 2 vrcholy
14) Vrchol P sousedí jedině se svým rodičem a vrcholem L1
15) Vrchol P má stupeň 2
16) Vrchol L1 sousedí jedině s vrcholem P
17) Vrchol L1 má stupeň 1
18) Jsme hotovi :o)

Pokud budou nejasnosti, napiš u které věty a proč.

lidi, nevedel by nekdo o nejakem lepsim postupu... nejak si s tim nevim rady. Hlavne s tim druhym prikladem...

↑ vilem:Zkus si přečíst alespoň některé příspěvky v tomto vlákně ;)

↑ leniczka:První obrázek je strom bez úplného párování, druhý graf s úplným párováním, který ale není strom. Obrázek jsem k tomu loni kreslil vašemu kolegovi:
Modré fleky jsou vrcholy, černé fleky párovací hrany a růžové fleky ostatní hrany. Omluvte sníženou kvalitu obrazu ;)

Co se týče bodu 9, tak ve stromě každý vrchol sousedí pouze s rodičem a dětmi. Protože Li nemají žádné potomky, sousdí pouze s rodičem.

Bod 10 využívá toho, že z každého vrcholu vychází nějaká párovací hrana (párování je úplné). Jediná hrana, která vychází z Li, vede do P, je proto párovací hranou.

Bod 11 vychází z toho, že kdyby existovaly vrcholy L1,L2 spojené s P, pak by podle bodu 10 hrany PL1 a PL2 byly párovací, což nelze. Proto je jen jeden vrchol Li, a to L1.

↑ vilem:Ano. A ještě jsem k tomu doplňoval pár poznámek (viz ↑ Kondr:).

ok takze ten obrazek, co si nakreslil vyse je bez uplneho parovani, podle bodu 10. Chapu to dobre? Jeste nejak nerozumim tomu bodu 13. Mohl by ho tu nekdo objasnit?? 

Toto je me zadani:

Nechť strom T na 2n, n≥2, vrcholech má úplné párování. Dokažte, že T má vrchol stupně 1, který je sousední s vrcholem stupně dva.
Poznámka: Úplné párování v grafu G je množina nezávislých hran (žádné dvě nemají společný koncový vrchol) v grafu G taková, že každý vrchol grafu G je koncovým vrcholem přesně jedné hrany tohoto párování.

Je mozna na to odpovedet, tak jak to tu rozepsal Kondr???

a co ten vrchol prvniho stupne, do ktereho vede pouze cervena hrana? z kazdeho vrcholu musi vezt parovaci hrana ne? nebo to uz neni potomek?

jj tak jsem to myslel :) ja jen, jestli to chapu dobre ;)

↑ gavec:Z toho, že k=1 neplyne, že graf má 3 vrcholy.  Navíc každý strom s úplným párováním, který má alespoň tři vrcholy, má alespoň 4 (počet vrcholů v grafu s úplnným párováním je sudý).