Matematické Fórum

Merlí · 29. 12. 2009 17:45

Ahoj
Potřeboval bych poradit se dvěma úlohama z grafů.

1) Dokažte, že každý konečný graf je izomorfní nějakému indukovanému podgrafu nekonečného grafu X=(N,E), kde {m,n} leží v E, pokud NSD(m,n)>1 (tedy se jedná o graf, kde vrcholy jsou přirozená čísla a hrany spojují soudělná čísla).

Řešení je v podstatě vidět z obrázku. Třeba libovolnou kružnici délky m tvoří postupně vrcholy x^1, x^2, ..., x^m. Problém je v tom, že nevím, jak to mám formulovat matematicky.

2) Najděte všechny grafy bez cesty délky 4 a dokažte, že jiné neexistují.

Grafy jsem našel a popsal. Jedná se:
a) o všechny grafy, kde v každé komponentě jsou nejvýš 2 vrcholy v, deg(v)>1 a ostatní mají stupeň 1 nebo 0
b) o všechny grafy, které obsahují právě 3 vrcholy v, deg(v)>1, přičemž tyto 3 vrcholy tvoří kružnici délky 3 a všechny ostatní vrcholy mají stupeň 1 nebo 0
Otázkou je, jak dokázat, že žádné další už neexistují...?

Díky

Olin · 29. 12. 2009 17:48 — Editoval Olin (29. 12. 2009 17:53)

A netvoří spíš $x, x^2, \dots, x^m$ úplný graf na $m$ vrcholech?

Kružnici bych spíš vytvořil tak, že bych vzal m různých prvočísel $p_1, p_2, \dots, p_m$ a vrcholy očísloval $p_1 p_2, p_2 p_3, \dots, p_{m-1} p_m, p_m p_1$ .

Merlí · 29. 12. 2009 17:59 — Editoval Merlí (29. 12. 2009 18:00)

Jo, máš pravdu, že x^1, x^2, ..., x^m tvoří úplný graf na m vrcholech. Toho jsem si nevšiml, protože jsem koukal jen na kružnice délky 3.
Každopádně to řešení s prvočísly moc nechápu.

Olin · 29. 12. 2009 18:06

No splňuje to to, co chceme. Zřejmě totiž pokud $\text{NSD}(p_a p_b, \, p_c p_d) > 1$ , pak musí platit alespoň jedna z těchto rovností:
$p_a = p_c\nl p_b = p_c\nl p_a = p_d\nl p_b = p_d$

Proto např. mezi $p_4 p_5$ a $p_5 p_6$ hrana vede ( $\text{NSD}(p_4 p_5, \, p_5 p_6) = p_5 > 1$ ), ale mezi $p_4 p_5$ a $p_6 p_7$ ne.

Merlí · 29. 12. 2009 18:22 — Editoval Merlí (29. 12. 2009 18:24)

Tak teď to chápu ještě míň.

Olin napsal(a):
Kružnici bych spíš vytvořil tak, že bych vzal m různých prvočísel

Olin napsal(a):
pokud NSD(pa, pb, pc, pd) > 1

- to nikdy nemůže být splněno, protože pi jsou různá prvočísla. A tedy žádná z rovností neplatí a tedy ani nevede hrana mezi p4p5 a p5p6... Ale asi jen špatně chápu co píšeš...?

Merlí · 29. 12. 2009 18:24

Ups, tam nejsou čárky... Tak jo, teď už to chápu.

Olin · 29. 12. 2009 18:30

Jo, mám to trochu namačkané na sebe, není to úplně čitelné. V tom rozboru $p_a,\, p_b,\, p_c,\, p_d$ se zabývám nějakými úplně obecnými prvočísly, které s těmi předchozími nemusí mít nic společného, to je asi také poněkud matoucí.

Merlí · 29. 12. 2009 19:11

Dobře, děkuju.
A ještě k tomu druhému příkladu...
Napadl mě postup dokazování, ale je to vlastně dedukce popisu všech grafů bez cesty délky 4.

Na začátku se omezíme jen na souvislé grafy. Pro nesouvislé grafy bychom totiž stejně posuzovali na existenci P4 každou komponentu zvlášť.
Teď:
a) graf obsahuje kružnici - tedy to může být pouze C3 (jinak by obsahoval P4) - ta obsahuje 3 vrcholy stupně 2 a na tyto 3 vrcholy můžu navázat libovolný počet vrcholů stupně 0. Pokud nyní mám souvislý graf, kde jsou 3 vrcholy stupně 2 na C3 a ostatní vrcholy mají stupeň 1 a přidám jakoukoliv hranu, tak mi už nutně vznikne cesta délky 4.
b) graf neobsahuje kružnici a dle dřívějšího je souvislý a tedy je to strom - aby strom neobsahoval P4, musí mít maximálně 2 vrcholy stupně >= 2 a všechny ostatní mají stupeň 1. Nyní kdybych přidal hranu, tak nutně vznikne kružnice (protože je to strom) a tím pádem posoudím graf dle případu a).

Zdá se mi to až moc jednoduchý - vidí v tom někdo nějaký problém? :-)

Olin · 30. 12. 2009 11:08

Jakou definici cesty používáš? Totiž podle mě by to mohla splňovat třeba i kružnice délky 4, řídím-li se tím, že v cestě se nesmí žádný vrchol vyskytnout dvakrát.

Merlí · 30. 12. 2009 23:09

Definice cesty je:

Code:

Cesta v grafu je sled v grafu, v němž se neopakují žádné hrany ani vrcholy.

Tedy je to posloupnost (v,e,v,e,v...), která začíná i končí vrcholem a mezi každým vrcholem je hrana.
Přitom kružnice délky 4 je posloupnost (v1, e1, v2, e2, v3, e3, v4, e4, v1). To ale nemůže být cesta, protože vrchol 1 je obsažen 2x.

Olin · 30. 12. 2009 23:16 — Editoval Olin (30. 12. 2009 23:16)

No ano, a my hledáme grafy, kde se cesta délky 4 nenachází, ne? A jak jsi právě napsal, v kružnici na 4 vrcholech cestu délky 4 nenajdeme.

Merlí · 30. 12. 2009 23:33

Hmm, máš pravdu.
Tedy ke grafům, které jsem vydefinoval, ještě přibyde graf C4 s jednou nebo oběma úhlopříčkami, je to tak?

Olin · 31. 12. 2009 11:22

Ještě mi není úplně jasný ten případ a). Mám C3 a na něj chci napojit další vrcholy. Ty ale můžu napojovat pouze na jeden z těch tří vrcholů, jinak by mi vznikla následující situace:

(červeně je vyznačená cesta).
Ale asi jsem jen nepochopil, jak to přesně myslíš.

Merlí · 01. 01. 2010 13:57

Spíš já jsem se nepřesně vyjádřil, ale takto jsem to myslel.
Díky

Matematické Fórum

#1 29. 12. 2009 17:45

2 grafové úlohy - izomorfismus a hledání cest

#2 29. 12. 2009 17:48 — Editoval Olin (29. 12. 2009 17:53)

Re: 2 grafové úlohy - izomorfismus a hledání cest

#3 29. 12. 2009 17:59 — Editoval Merlí (29. 12. 2009 18:00)

Re: 2 grafové úlohy - izomorfismus a hledání cest

#4 29. 12. 2009 18:06

Re: 2 grafové úlohy - izomorfismus a hledání cest

#5 29. 12. 2009 18:22 — Editoval Merlí (29. 12. 2009 18:24)

Re: 2 grafové úlohy - izomorfismus a hledání cest

Olin napsal(a):

Olin napsal(a):

#6 29. 12. 2009 18:24

Re: 2 grafové úlohy - izomorfismus a hledání cest

#7 29. 12. 2009 18:30

Re: 2 grafové úlohy - izomorfismus a hledání cest

#8 29. 12. 2009 19:11

Re: 2 grafové úlohy - izomorfismus a hledání cest

#9 30. 12. 2009 11:08

Re: 2 grafové úlohy - izomorfismus a hledání cest

#10 30. 12. 2009 23:09

Re: 2 grafové úlohy - izomorfismus a hledání cest

Code:

#11 30. 12. 2009 23:16 — Editoval Olin (30. 12. 2009 23:16)

Re: 2 grafové úlohy - izomorfismus a hledání cest

#12 30. 12. 2009 23:33

Re: 2 grafové úlohy - izomorfismus a hledání cest

#13 31. 12. 2009 11:22

Re: 2 grafové úlohy - izomorfismus a hledání cest

#14 01. 01. 2010 13:57

Re: 2 grafové úlohy - izomorfismus a hledání cest

Zápatí