Adjuk meg ennek a gráfnak a minimális súlyú feszítőfáját a Kruskal-algoritmus segítségével.
Térképezzük föl az alábbi gráfot a szélességi bejárás (BFS) segítségével.
Térképezzük föl az alábbi gráfot a mélységi bejárás (DFS) segítségével.
a) Íme, egy gráf két különböző kezdőpontjából készített BFS fája:
Adjuk meg az eredeti gráfot.
b) Egy gráfban minden csúcs fokszáma páros, és két különböző kezdőpont alapján készített BFS fája:
Adjuk meg az eredeti gráfot.
a) Létezik-e az alábbi gráfban Hamilton kör?
b) Létezik-e az alábbi gráfban Hamilton út?
Adjuk meg az alábbi gráfban az A és D csúcsok távolságát.
Térképezzük föl az alábbi gráfot a Dijkstra algoritmus segítségével.
a) A BFS algoritmus az alábbi ábra gráfjának csúcsait a következő sorrendben járta be: S, _ , _ , _ , H, _ , F, C, _ . Egészítsük ki a sorozatot a hiányzó csúcsok neveivel és adjuk meg a bejáráshoz tartozó BFS fát.
b) Az ábrán látható gráf egyik élét elhagytuk. Az él elhagyása előtt S-ből indított BFS algoritmus a gráf csúcsait az alábbi sorrendben járta be:
i) S, B, I, C, A, F, H, E, D
ii) S, I, B, E, D, H, C, A, F
Megállapítható-e egyértelműen, hogy melyik élt hagytuk el? Ha igen, akkor adjuk meg a bejáráshoz tartozó BFS-fát is.
a) Bizonyítsuk be, hogy minden 4-nél nagyobb n számra van olyan n csúcsú G gráf, hogy G-ben és a komplementerben is van Hamilton kör.
b) Egy 100 csúcsú egyszerű gráfban két nem szomszédos csúcs foka 49, az összes többi csúcs foka legalább 50. Bizonyítsuk be, hogy van a gráfban Hamilton út.
c) Mit mondhatunk arról a 101 pontú gráfról, amiben minden csúcs foka legalább 50. Van-e a gráfban Hamilton út?
a) Derítsük ki, hogy van-e az alábbi gráfban Hamilton kör. Ha nincs, akkor minimum hány újabb élt kell hozzávennünk ahhoz, hogy legyen?
b) Derítsük ki, hogy van-e az alábbi gráfban Hamilton kör. Ha nincs, akkor minimum hány újabb élt kell hozzávennünk ahhoz, hogy legyen?
c) Minimum hány élt kell behúznunk ebben a gráfban, hogy legyen benne Hamilton kör?
d) Adott egy 100 csúcsú egyszerű gráf, amiben két szomszédos csúcs foka 49, az összes többi csúcs foka pedig legalább 50. Bizonyítsuk be, hogy van a gráfban Hamilton út.
a) Döntsük el, hogy az alábbi gráfnak van-e Hamilton köre, illetve Hamilton útja.
b) Van-e az alábbi gráfban olyan Hamilton kör...
i) ami nem tartalmazza az {A,B} élt?
ii) ami nem tartalmazza a {C,D} élt?
c) Döntsük el, hogy az alábbi gráfnak van-e Hamilton köre, illetve Hamilton útja.
d) 1001 pontú gráf minden csúcsa legalább 501 fokú, kivéve egyetlen csúcsot, aminek a fokszáma 500. Bizonyítsuk be, hogy a gráfban van Hamilton kör.
e) Döntsük el, hogy az alábbi gráfnak van-e Hamilton köre, illetve Hamilton útja.
a) A $G$ egyszerű gráf csúcshalmaza legyen $V(G)=\{1, 2, \dots, 10 \}$. Az $x,y \in V(G)$, $x \neq y$ csúcsok pontosan akkor legyenek szomszédosak $G$-ben, ha $ \mid x - y \mid \leq 2 $.
Van-e $G$-nek olyan feszítőfája, hogy összes éle olyan, amelyre $ \mid x-y \mid = 2$ teljesül?
b) A $G$ egyszerű gráf csúcshalmaza legyen $V(G)=\{1, 2, \dots, 10 \}$. Az $x,y \in V(G)$, $x \neq y$ csúcsok pontosan akkor legyenek szomszédosak $G$-ben, ha $ \mid x - y \mid =2 $ vagy $\mid x-y \mid = 3$.
Van-e $G$-ben Hamilton út, illetve Hamilton kör?
a) Egy 100 csúcsú $G$ összefüggő gráf éleit az 1 és 2 súlyokkal súlyoztuk úgy, hogy az 1 súlyú élek részgráfja (vagyis az a gráf, melynek csúcsai azonosak $G$ csúcsaival, de annak csak az 1 súlyú éleit tartalmazza) 7 komponensből áll.
Határozzuk meg $G$ egy minimális összsúlyú feszítőfájának súlyát.
b) Egy 100 csúcsú összefüggő, egyszerű gráfnak 101 éle van. Mutassuk meg, hogy ekkor van a gráfban 3 páronként különböző feszítőfa. (Két feszítőfa akkor különböző, ha nem pontosan ugyanazon élek alkotják.)
