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
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
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
Příspěvky: 4691
Škola: PřF MUNI
Reputace:   220 
 

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: 3275
Reputace:   90 
 

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ě.


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#3 10. 02. 2016 19:07

byk7
InQuisitor
Příspěvky: 4691
Škola: PřF MUNI
Reputace:   220 
 

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: 3275
Reputace:   90 
 

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)?


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#5 13. 02. 2016 19:47

byk7
InQuisitor
Příspěvky: 4691
Škola: PřF MUNI
Reputace:   220 
 

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