Matematické Fórum

Jana86 · 14. 12. 2007 18:13

Dobrý den,
chtěla bych poprosit o pomoc s tímto příkladem.
Děkuji.

Pro každé 1 ≤ a ≤ b ≤ c ∈ N najděte příklad grafu, který má vrcholový stupeň souvislosti a, hranový stupeň souvislosti b a nejmenší stupeň c.

Saturday · 14. 12. 2007 18:53

Předpokládám, že "c" značí stupně vrcholů, resp. minimální stupeň u vrcholů - pokud to tak není, tak to zkus prosím upřesnit, co je tím míněno; dále přepokládám, že tímto: "vrcholový stupeň souvislosti a, hranový stupeň souvislosti b" je myšlena maximální souvislost grafu (např. graf, který je 3-souvislý je zároveň 2-souvislý)

Vyjdeme z definicí:

Graf G nazveme vrcholově k-souvislý, má-li aspoň k + 1 vrcholů a odebráním libovolných nejvýše k - 1 vrcholů vždy dostaneme souvislý graf.
Graf G nazveme hranově k-souvislý, pokud po odebrání libovolných nejvýše k - 1 hran zůstane graf souvislý.

Příkladem může být kružnice délky 3 (trojúhelník), označme si ho G.

Graf G je vrcholově 2-souvislý a zároveň hranově 2-souvislý a zároveň všechny vrcholy mají stupeň 2, tedy zadání je splněno.

Pro kružnici délky 4 by podmínka ze zadání splněna nebyla, protože graf je vrcholově 3-souvislý a hranově 3-souvislý a přitom má stupně vrcholů 2.

Doufám, že je to srozumitelné, pokud ne, tak se zkus zeptat, popř. počkej na pomoc od nějakého kolegy.

Jana86 · 14. 12. 2007 19:43

1)"c" značí stupně vrcholů

2)Vrcholový stupeň souvislosti grafu je minimální počet vrcholů, jejichž odstraněním vznikne graf nesouvislý nebo složený z jediného vrcholu
Graf G je vrcholově k-souvislý,k>1,pokud i po odebrání libovolných k-1 vrcholů z G zůstane výsledný graf souvislý.

3)Hranový stupeň souvislosti grafu je minimální počet hran, jejichž odstraněním vznikne graf nesouvislý nebo složený z jediné hrany.
Graf G je hranově k-souvislý,k>1,pokud i po odebrání libovolných k-1 hran z G zůstane výsledný graf souvislý.

Jana86 · 14. 12. 2007 20:53

Pokud jsem to vše dobře pochopila tak podmínky zadání by měl splnit i tento graf,který je, pokud se nepletu také vrcholově 2-souvislý a zároveň hranově 2-souvislý a zároveň všechny vrcholy mají stupeň 2.

http://matematika.havrlant.net/forum/up … -Graf3.jpg

Saturday · 14. 12. 2007 21:50

ano, ten splnuje to, co rikas :-) obecně pro kružnice to musí platit vždy (všechny vrcholy mají stupeň dva a pokud odebereš dva vrcholy nebo dvě hrany tak není souvislý)

K těm definicím, na přednáškách jsem neměl: Vrcholový stupeň souvislosti grafu a Hranový stupeň souvislosti grafu.. jen tu definici, kterou jsem psal já.. původně jsem myslel, že je to to samé a ono je, i když ta definice je vyslovená jinak.

Jana86 · 14. 12. 2007 22:04

Děkuji Vám moc za pomoc při řešní.

Kondr · 14. 12. 2007 22:21

No tak to by bylo řešení pro konkrétní trojici (a,b,c)=(2,2,2). V zadání je ale pro všechny trojice nalezněte...
což je výrazně těžší.

Saturday · 15. 12. 2007 00:08

Toho jsem si bohuzel nevsiml

Jediné, na co jsem zatím přisel je to, že pokud mám úplný graf s n+1 vrcholy, který je vždy vrcholově n-souvislý a pak vytvořím násobné hrany mezi vrcholy (libovolné dva vrcholy grafu mají x hran spojující tyto dva vrcholy), pak je výsledný graf x*n-hranově souvislý.

Pokud pak zase začnu odebírat hrany, stačí odebírat např. hranu {1,2}, pak se snižuje minimální stupeň grafu (=c) a zároveň i hranová souvislost grafu.

Dokážu tedy vytvořit graf, který splňuje: 1<=a<=b<=c za podmínky, že b=c ...

Ještě je tedy třeba umět zafixovat "c" a pak to obalit do nějakého hezčího hávu..

Jana86 · 15. 12. 2007 10:41

Tak se dobrovolně přiznám že toho "Pro každé" jsem si všimla také až teď.
Už se mě ten příklad nezdá tak jednoduchý.Momentálně přemýšlím jak najít příklad pro všechny možnosti, které splňují podmínku 1 ≤ a ≤ b ≤ c ∈ N
a jde mě z toho hlava kolem:-)

Kondr · 11. 01. 2008 00:18

Co kdybychom zkusili toto: vyrobíme dva úplné grafy o c+1 vrcholech. V jednom zvolíme a vrcholů, ve druhém b vrcholů. Pak pro i od 1 do b spojíme i-tý z těchto b vrcholů s
((i mod a)+1)-tým vrcholem ze zvolené a-tice vrcholů. Věřím, že toto funguje (vyjma případu a=b=c, který je triviální). Věříte také?

Matematické Fórum

#1 14. 12. 2007 18:13

Teorie grafů

#2 14. 12. 2007 18:53

Re: Teorie grafů

#3 14. 12. 2007 19:43

Re: Teorie grafů

#4 14. 12. 2007 20:53

Re: Teorie grafů

#5 14. 12. 2007 21:50

Re: Teorie grafů

#6 14. 12. 2007 22:04

Re: Teorie grafů

#7 14. 12. 2007 22:21

Re: Teorie grafů

#8 15. 12. 2007 00:08

Re: Teorie grafů

#9 15. 12. 2007 10:41

Re: Teorie grafů

#10 11. 01. 2008 00:18

Re: Teorie grafů

Zápatí