Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 09. 02. 2016 16:24

byk7
InQuisitor
Místo: Břeclav, Brno
Příspěvky: 4455
Škola: PřF MUNI, konzervatoř Brno
Pozice: student
Reputace:   216 
 

Teorie grafů

Označme $H[X]$ podgraf souvislého (neorientovaného, jednoduchého) grafu $G=(V,E)$ indukovaný množinou $X\subseteq V$. Dokažte, že existuje neprázdná podmnožina vrcholů $X$ splňující $|E(H[X])|+|E(H[V\setminus X])|<\frac12|E(G)|$.


Příspěvky psané červenou barvou jsou moderátorské, šedá je offtopic.

Offline

  • (téma jako vyřešené označil(a) byk7)

#2 10. 02. 2016 18:50

check_drummer
Příspěvky: 2397
Reputace:   65 
 

Re: Teorie grafů

↑ byk7:
Ahoj, co zkusit pravděpodobnostní postup? Volit X náhdoně a spočítat střední hodnotu (nebo její odhad) pro ten součet na levé straně. Případně uvažovat jen ty G, pro které nelze X nalézt triviálně.


Achilleovo tvrzení: Ocitl jsem se v patové situaci.

Offline

 

#3 10. 02. 2016 19:07

byk7
InQuisitor
Místo: Břeclav, Brno
Příspěvky: 4455
Škola: PřF MUNI, konzervatoř Brno
Pozice: student
Reputace:   216 
 

Re: Teorie grafů

↑ check_drummer:

Díky, vyzkouším, až budu mít čas. Nicméně ta úloha by měla být řešitelná nějakým elementárním postupem, který mi uniká.


Příspěvky psané červenou barvou jsou moderátorské, šedá je offtopic.

Offline

 

#4 10. 02. 2016 21:45

check_drummer
Příspěvky: 2397
Reputace:   65 
 

Re: Teorie grafů

↑ byk7:
Co zkusit maximální párování a vrcholy na koncích hran toho párování definovat množinu X (resp. V\X)?


Achilleovo tvrzení: Ocitl jsem se v patové situaci.

Offline

 

#5 13. 02. 2016 19:47

byk7
InQuisitor
Místo: Břeclav, Brno
Příspěvky: 4455
Škola: PřF MUNI, konzervatoř Brno
Pozice: student
Reputace:   216 
 

Re: Teorie grafů

Tak prý indukce. Nerovnost si upravíme do tvaru $|E(H[X])|+|E(H[V\setminus X])|<|E(G)|-|E(H[X])|-|E(H[V\setminus X])|$
(na pravé straně tak dostáváme hrany vedoucí pouze mezi podgrafy $H[X]$ a $H[V\setminus X]$).

1) Nechť je $|V|=3$, možnosti jsou jen dvě: cesta $P_3$ a cyklus $C_3$, existence množiny $X$ je pak zřejmá.
2) Nechť je $G$ graf vyhovující zadání a $v\in V$. Z indukčního předpokladu umíme graf $G\setminus v$ rozdělit. Vrchol $v$ pak dáme do množiny, kde mám méně sousedů. Pokud jich má v obou stejně, pak ho umístíme libovolně.


Příspěvky psané červenou barvou jsou moderátorské, šedá je offtopic.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson