Matematické Fórum

Ginco · 30. 06. 2010 10:52 — Editoval Ginco (30. 06. 2010 10:54)

ahoj všem, mám před zkouškou a zjistil jsem, že bych potřeboval aspoň trochu poradit s některýma věcma. Kdyby byl někdo tak hodný a poradil, byl bych mu vděčen..

1. Najděte automorfismy následujícího grafu...to vubec netuším jak se udělá...

2. Jak by se u takového příkladu třeba našel prostor kružnic?

3. Jak se určí matice vážených vzdáleností? (w-distanční matice)?
Četl jsem, že se dá zkonstruovat pomocí Dijkstrova algoritmu, který umím, ale nevím jak to zkombinovat.

Moje zkouška je spíše počítací, proto jsem celkem oželel teorii, čehož ted lituju, každopádně za každou radu jsem velmi rád...děkuji všem...

spm · 30. 06. 2010 12:07

3) jestli chápu správně, tak v té matici by na místě i, j měla být nejkratší vzdálenost z vrcholu i do j. Dijkstrův algoritmus dokáže určit z jednoho pevně daného vrcholu nejkratší cestu do všech ostatních. Pokud se tedy pustí n-krát, lze s ním vypočítat nejkratší vzdálenosti mezi každými dvěma vrcholy (a tedy snad i to, co by mělo být v té matici).

ondrej.hav · 30. 06. 2010 12:41

↑ Ginco:K určení prostoru(fundamentálního prostoru) kružnic se používá podobný postup který jsem popisoval Zde Pokud z toho nepochopíš, ještě rozepíšu na případ kružnic...

w-distanční matice: Spojitost s dijkstrem neznám.... Ale pokud si uděláme váženou matici sousednosti, která je definovaná takto:

$W(G): w_{i,j}= \begin{cases} w, & \text{pokud vede z vrcholu hrana}\nl 0, & \text{jinak} \end{cases}$

Kde w je ohodnocení té hrany (používá se samosebou jen na ohodnocení grafy)

Pak jí upravíš tak, že nuly mimo diagonálu změníš na $\infty$ a provádíš takové "speciální umocňování" kdy místo operace násobení pouzíváš plus a místo operace sčítání používáš minimum...

Celý to umocnění musíš provést $(n-2)*$ Vlastně nejvýše $(n-2)*$ ale to je zatím jedno...

Pokud sem dáš nějaký lehký ohodnocený graf na nejvýše 4 vrcholech, tak se můžu pokusit to tu vyřešit...

Doporučoval bych ti jako všem, aby si se podíval do nějakých skript DMA. Například ty co napsal pan Brousek z roku 95 jsou dobrý a popis vytvoření w-dist. matice tam je popsaný.

nazávěr sem dám odkaz na pdf ve kterým se tuto taky řeší... na straně 35 Odkaz

Ginco · 30. 06. 2010 13:34

↑ ondrej.hav:

cus díky za reakci...

co se týče prostoru kružnic, tak jsem našel nějakej postup

1. v grafu si vyznačím kostu
2. vezmu prvni hranu, ktera neni v kostre a snazim se pres ni udelat kruznici pomoci jiz pripravene kostry.. tam, kde je "zvyrazneno"(tim se mysli doplneni na kruznici) tak ty slozky tech bazovych prvku budou jednicky a tam kde nepotrebuji zvyraznenou hranu abych dostal kostru budou nuly.
3 tento postup opakuji dokud nedoplnim vsechny hrany ktere netvorili kostru na kruznici a vyjdou mi nejake asi vektory...baze kruznic, ta se pak zapisuje do matice nebo jen jako vektory? a tot vse?

vim ze je to takove neomalene, ale snad je to v tom citit a snad je to aspon trochu spravne

zkusim nakreslit

takze e_7 = [0 1 1 0 0 0 1] a e_6 = [1 1 0 0 0 1 0] je to tedy baze kruznic toto?

co se tyce w-distancni matice tak co tenhle priklad, zvladnes to trochu popsat abych to pochopil?

já jdu právě zejtra k Brusičovi a asi to bude masakr...plno veci jeste neumim, kouknu jeste na ty materialy z ulozto, to jsou stejne priklady ke zkousce vid?

ondrej.hav

↑ Ginco:
Dobře...
Zkusím trošku rozepsat ten prostor kružnic...

Pokud se dostaneš k výsledku měl by si dostat $E(G)-V(G)+1$ vektorů (ve tvém případě 10-6+1 = 5), které generují prostor všech kružnic toho grafu...
Ty se buďto zapíšou do matice (dostaneš matici kružnic) nebo prostě řekneš, že to jsou vektory generující f.prostor kružnic.

A hlavně jich máš málo... Kam se ti poděly ty tři hrany v pravém "čtverci"?

Důležité je taky očíslování. Pokud hledáš prostor kružnic, tak nejdříve čísluješ hrany mimo kostru... Aby si pak vlastně neměl vekory $e_6$ $e_7$ ale klasicky číslované od jedničky...

Jak jsem již psal bude těch vektorů 5.. tudíž budu mít matici o 5ti řádcích a 10ti sloupcích (celkový počet hran)..
$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & x & x & x & x & x\nl 0 & 1 & 0 & 0 & 0 & x & x & x & x & x\nl 0 & 0 & 1 & 0 & 0 & x & x & x & x & x\nl 0 & 0 & 0 & 1 & 0 & x & x & x & x & x\nl 0 & 0 & 0 & 0 & 1 & x & x & x & x & x\nl \end{pmatrix}$

Jinak to co jsi napsal o tom "doplňování" matice by mělo být správně... Zkus sem tedy hodit nějaké řešení a já ti ho zkontroju...

P.S.: Zvlášť u pana Brouska je důležité aby si měl tu matici zapsanou tak jako já. To znamená aby na začátku měla jednotkovou podmatici... ono když by si ty vektory nějak přeházel tak je to jedno, pořád to generuje ten samý prostor, ale jemu se to líbí takhle a co se mu líbí je na zkoušce svatý.

P.S.2: Pokud si se vůbec neučil teorii doporučil bych ti aspoň dvě věci Stoenova věta o reprezentaci a Atom booleovy algebry. To on zkouší rád... BTW. myslím si, že teorie a Skripta ti na DMA pomohou hodně, ale s tím už nic nenaděláš no jestli máš poslední den...

Když pak vezmu ten druhý příklad...

tak když si sestavím tu matici... Předpokládám že vrcholy jsou očíslované tak že vrchol 1 je ten co je vpravo dole, vlevo dole 2 atd... Ten graf není orientovaný což je divné, ale neni to překážka. pokdu není orientovaný, zavedeme jeho symetrickou orietnaci.

$\begin{pmatrix} 0 & 4 & 3 & \infty \nl 4 & 0 & 2 & 2 \nl 3 & 2 & 0 & 1 \nl \infty & 2 & 1 & 0 \nl \end{pmatrix}$
Pokud byl graf původně neorientovaný, tak ta matice bude symetrická to je asi jasný...

No a ted to (spešl umocnění)... Pokud umíš násobit mezi sebou matice tak zkus $\begin{pmatrix} 0 & 4 & 3 & \infty \nl 4 & 0 & 2 & 2 \nl 3 & 2 & 0 & 1 \nl \infty & 2 & 1 & 0 \nl\end{pmatrix}$ $\cdot$ $\begin{pmatrix} 0 & 4 & 3 & \infty \nl 4 & 0 & 2 & 2 \nl 3 & 2 & 0 & 1 \nl \infty & 2 & 1 & 0 \nl\end{pmatrix}$

Ale použij ty operace které sem napsal...

Pro ukázku první řádek matice bude 0, 4, 3, 4... napiš výsledek a zase to zkontroluju..

Ginco · 30. 06. 2010 14:14

↑ ondrej.hav:

tak jako ty hrany v pravem ctverci tam nejsou ani nebyli...to černe vytazene(slabe je to ja vim) je puvodni graf, cervnene kostra...takze si myslim, ze to nakonec mam dobre

ondrej.hav · 30. 06. 2010 14:35

↑ Ginco:Uplne nahore je nejaky graf.. myslel jsem, ze to chces urcovat k nemu...Jestli ne, tak se omlouvam...

Ginco · 30. 06. 2010 14:45

↑ ondrej.hav:

:-) nemas se za co omlouvat ondro, pomohl jsi mi...hele ale kdybych tedy mel jen 2 bazove prvky, tak jak by vypadala ta matice v mém pripade? to jak jsi psal? protoze mám 7 hran, takze ty prvky by meli být 7mi slozkove ne? ale jak tam mas to x x x x x tak to ma jen 5 slozek...nejak jsem to nepochopil....

ten graf byl k automorfismum, ktere nevim jak urcim.... stejne jako urcit homomorfismy 2 grafu...

chtel jsem se zeptat na ta skripta pana Brouska z roku 95 jsou nekde v ele. podobe?

díky

ondrej.hav · 30. 06. 2010 14:59

↑ Ginco:No ty vektory budou mit 7 slozek... bude to obsahovat jednotkovou podmatici velikosti 2... To je právě to cyklomatické číslo.. $E(G)-V(G)+1$ takže ta matice bude vypadat takhle...
$\begin{pmatrix} 1 & 0 & x & x & x & x & x\nl 0 & 1 & x & x & x & x & x\nl \end{pmatrix}$

Právě je důležité si uvědomit jak a proč to tak je...

No Skripta urcite nekde jsou... Ja osobne mam ty novejsi od Ryjáčka... Jeslti chces hodi, je na ulozto.

Ginco · 30. 06. 2010 15:12 — Editoval Ginco (30. 06. 2010 15:13)

$D_2 = D_1 * D_1 = \begin{pmatrix} 0 & 4 & 3 & \infty \nl 4 & 0 & 2 & 2 \nl 3 & 2 & 0 & 1 \nl \infty & 2 & 1 & 0 \nl\end{pmatrix}.\begin{pmatrix} 0 & 4 & 3 & \infty \nl 4 & 0 & 2 & 2 \nl 3 & 2 & 0 & 1 \nl \infty & 2 & 1 & 0 \nl\end{pmatrix} = \begin{pmatrix} 0 & 4 & 3 & 4 \nl 4 & 0 & 2 & 2 \nl 3 & 2 & 0 & 1 \nl 4 & 2 & 1 & 0 \nl\end{pmatrix}$

1. radek

[0 4 3 oo].[0 4 3 oo]= min[0, 8 6 oo]= 0
[0 4 3 oo].[4 0 2 2]= min[4, 4, 5, oo]= 4
[0 4 3 oo].[3 2 0 1]= min[3, 6, 3, oo]= 3
[0 4 3 oo].[oo 2 1 0] = min[oo, 6 4, oo]= 4
-------------------------------------------------------
2.radek

[4 0 2 2].[0 4 3 oo] = min[4, 4 5 oo]= 4
[4 0 2 2].[4 0 2 2] = min[8,0 ,4, 4] = 0
[4 0 2 2].[3 2 0 1]= min[7, 2, 2,3]= 2
[4 0 2 2].[oo 2 1 0]= min[oo, 2, 3,2]= 2
------------------------------------------------------
3.radek

[3 2 0 1].[0 4 3 oo] = min[3, 6,3,oo]=3
[3 2 0 1].[4 0 2 2]=min[7 2 2 3]= 2
[3 2 0 1].[3 2 0 1]= min[6, 4, 0, 2]= 0
[3 2 0 1].[oo 2 1 0]= min[oo, 4, 1, 1]=1
-----------------------------------------------------
4.radek

[oo 2 1 0].[0 4 3 oo] = min[oo, 6, 4,oo]=4
[oo 2 1 0].[4 0 2 2]=min[oo, 2, 3, 2]= 2
[oo 2 1 0].[3 2 0 1]= min[oo, 4, 1, 1]= 1
[oo 2 1 0].[oo 2 1 0]= min[oo,4, 2,0 ]=0

No a ted vím, že $D_3 = D_1 * D_2$ a do kdy to opakuji?

dik ta skripta mám pred sebou, já vím, ze je dulezite vedet proc to tak je...jeste se to dneska naucim(z casti) :-(

ondrej.hav · 30. 06. 2010 15:17

↑ Ginco:Musíš to opakovat $(n-2)*$ Ale často se stane (poznáš u větších matic) že se ta matice začne opakovat. Pak můžeš to umocňování ukončit... Což je logický.... taky se ti ta matice nezopakovala... D_3 =! D1 a tak to musíš zopakovat...

Ginco · 30. 06. 2010 15:21 — Editoval Ginco (30. 06. 2010 15:22)

↑ ondrej.hav:
$\begin{pmatrix} 1 & 0 & x & x & x & x & x\nl0 & 1 & x & x & x & x & x\nl\end{pmatrix}$

ted ale nevim jak tam doplnit ty jednicky a nuly aby mi to vyslo...nejak se mi to nedari...pokud to chapu(jako ze asi ne), tak prvni radek te jednotkove podmatice mi dává informaci o 1. a 2. hraně...to pak ale nejde...nevím, zkus mi prosim poradit

n je řád matice? pokud ano, tak je mi tento priklad po početní stránce jasny

ondrej.hav · 30. 06. 2010 17:05

↑ Ginco:Takže jsem si očísloval ten graf... Zvolil jsem si kostru jako ty a uhlopricku z leveho horniho rohu jsem označil 1 a tu druhou 2... Zbytek jsme očísloval 3-7 ve stejném pořadí jako ty...

Pokud tedy vezmu tu hranu jedna, musím přidat hrany 4 a 5 aby mi vznikla kružnice... musím přidávat pouze hrany kostry, aby mi tam zůstala ta jednotková podmatice...

pokud vemu hranu 2 musím přidat hrany 3 a 4.

$\begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 0 & 0\nl0 & 1 & 1 & 1 & 0 & 0 & 0\nl\end{pmatrix}$

No a z toho bych měl být schopnej sestavit jakoukoli kružnici. Tohle je divnej graf. Nevypadá jako od brouska... takže ten fundamentalni prostor vlastně ukazuje všechny kružnice toho grafu. Žádné nejsou "skraté" takže ti neukážu jak je z toho dostat...

Důležité taky je, že počet jedniček v jednom vektoru je vždy lichý.

A že každy vektor tohohle prostoru je kolmý k jakémukoli vektoru prostoru řezů... uf...

ondrej.hav · 30. 06. 2010 17:07

↑ Ginco:
A ano n je řád matice.. Lepší je ale používat výraz V(G). Tzn počet vrcholů. Jsou to sice stejný čísla ale definice je podle počtu vrcholů a ne podle řádu matice sousednosti...

Ginco · 30. 06. 2010 18:32 — Editoval Ginco (30. 06. 2010 18:33)

↑ ondrej.hav:

jasně, problém byl v tom, že mě nenapadlo si ty hrany toho grafu očíslovat jinak, aby to vycházelo, jak jsi psal výše, ted to již chápu(snad)

nejpre si načrtnout kostru, zjistit cyklomatické číslo, a podle toho jaké to číslo vyjde (např. 3), tak ty hrany které nejsou v kostre, tak je ocislovat(vhodne) a doplnit, pamatovat si, ze pocet "jednicek" musi byt lichy a že každý vektor z prostoru kružnic daného grafu je ortogonální ke všem řezům grafu...

ondrej.hav · 30. 06. 2010 18:37

↑ Ginco:Jj pokud vyjde C.č. 3 tak bude nejdříve jednotková podmatice velikosti 3 a pak zbytek...

Matematické Fórum

#1 30. 06. 2010 10:52 — Editoval Ginco (30. 06. 2010 10:54)

příklady z diskrétní matematiky

#2 30. 06. 2010 12:07

Re: příklady z diskrétní matematiky

#3 30. 06. 2010 12:41

Re: příklady z diskrétní matematiky

#4 30. 06. 2010 13:34

Re: příklady z diskrétní matematiky

#5 30. 06. 2010 14:08 — Editoval ondrej.hav (30. 06. 2010 14:35)

Re: příklady z diskrétní matematiky

#6 30. 06. 2010 14:14

Re: příklady z diskrétní matematiky

#7 30. 06. 2010 14:35

Re: příklady z diskrétní matematiky

#8 30. 06. 2010 14:45

Re: příklady z diskrétní matematiky

#9 30. 06. 2010 14:59

Re: příklady z diskrétní matematiky

#10 30. 06. 2010 15:12 — Editoval Ginco (30. 06. 2010 15:13)

Re: příklady z diskrétní matematiky

#11 30. 06. 2010 15:17

Re: příklady z diskrétní matematiky

#12 30. 06. 2010 15:21 — Editoval Ginco (30. 06. 2010 15:22)

Re: příklady z diskrétní matematiky

#13 30. 06. 2010 17:05

Re: příklady z diskrétní matematiky

#14 30. 06. 2010 17:07

Re: příklady z diskrétní matematiky

#15 30. 06. 2010 18:32 — Editoval Ginco (30. 06. 2010 18:33)

Re: příklady z diskrétní matematiky

#16 30. 06. 2010 18:37

Re: příklady z diskrétní matematiky

Zápatí