Matematické Fórum

prespic · 12. 12. 2011 15:35

Dobrý den. Jako asi hodně lidí tady, jsem bezradně ztracen.
Prošvihl jsem odevzdání projektu a tak jsem nucen vypracovat těžší verzi:

Odkaz

První příklad zatím neřeším, moc látce nerozumím.
Jde mi hlavně o druhý příklad. Zde je mi jasné oč jde, ale nevím jak to dokázat.

Mohl by mi prosím někdo pomoct, nebo mě alespoň nakopnout? Moc by mi to pomohlo.

Předem všem děkuji.

OiBobik · 12. 12. 2011 18:38

↑ prespic:

Ahoj, pakliže jste něco takového probírali, bude určitě rozumné se opřít o odhady počtu hran rovinného grafu.

petrkovar · 12. 12. 2011 20:07

↑ OiBobik: Samozřejmě jsme to probírali :),
konkrétně na 10. přednášce.
Pro první příklad se mohou hodit poznámky z druhé přednášky, nebo některý z učebních textů.

prespic

Děkuji za reakce.

EDIT: Zapoměl jsem říct, že vycházím z nejmenšího možného grafu, což je $G = \{5.4.4.3.3.3\}$
kde $|E| = 11$ a $|V| = 6$ ... což, mě teď napadlo, asi bude chyba, protože může existovat $G = \{6,6,6,6,5,3,3,3\}$

Nakonec jsem dospěl k (kupodivu velice jednoduchemu) vzorci, pro přidání vrcholu stupně 4: $11+2n \le 12 + 2n -4$ . Ten vychází $0 \le -3$ což je nepravda. Obdobně, pro přidání vrcholu stupně 6 $11+3n \le 12 + 2n -4$ s výsledkem $n\le -3$ což je v oboru celých čísel také není pravda.

Důsledek: Pro přidání libovolného počtu těchto vrcholů neplatí podmínka $|E| \le 2|V| -4$ , což znamená, ža musí obsahovat C3.

Mohu toto považovat za dostatečný důkaz zadání? Respektive, je to vůbec správně?

petrkovar · 14. 12. 2011 00:13

↑ prespic:Ne, toto není úplný důkaz. Zdá se, že vycházíte (z nevysloveného) předpokladu, že všechny grafy splňující parametry zadání lze získat přidáváním vrcholů stupně čtyři do některého ze dvou grafů s uvedenou stupňovou posloupností. To není pravda. Uměl bych sestavit NEKONEČNE mnoho jdalších grafů.

Ale jste na správné cestě. Jen je třeba oprostit se od konkrétních instancí grafů.

Matematické Fórum

#1 12. 12. 2011 15:35

Teorie grafu - dukaz, ze graf obsahuje C3

#2 12. 12. 2011 18:38

Re: Teorie grafu - dukaz, ze graf obsahuje C3

#3 12. 12. 2011 20:07

Re: Teorie grafu - dukaz, ze graf obsahuje C3

#4 13. 12. 2011 23:20 — Editoval prespic (13. 12. 2011 23:33)

Re: Teorie grafu - dukaz, ze graf obsahuje C3

#5 14. 12. 2011 00:13

Re: Teorie grafu - dukaz, ze graf obsahuje C3

Zápatí