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 17. 06. 2012 15:47 — Editoval RePRO (17. 06. 2012 16:10)

RePRO
Místo: Jihlava
Příspěvky: 363
Škola: AI VŠPJ (09-12, Bc.)
Pozice: programátor
Reputace:   11 
Web
 

smíšené příklady

Zdravím,
potřebuji spíše pomoci, nejde mi o přesný výpočet... Vždy napíšu, o co se snažím, díky.

1. Kolik různých úplných podgrafů K4 existuje v úplném grafu K5?
K4 má 4 vrcholy a 6 cest (hran).
K5 má 5 vrcholů a 10 cest (hran).
Btw: Jak spočítám matematicky počet hran?

Permutace 4 * 6?
Krát 6 dávám z toho důvodu, že ty hrany drží pospolu, jestli se to tak dá napsat.
Permutace 4 dávám z toho důvodu, že zbývají 4 volné místa, kde se může permutovat.

2. Homogenní soustava rovnic (víc rovnic, jak neznámých)
Při 4 rovnicích a 3 neznámých, bych si jeden řádek odmyslel. OK, nebo jiná alternativa?
Při 3 rovnicích a 4 neznámých počítám jak?
Asi bych se koukl i na počet řešení dle geeka Frobenia, tedy dle Frobeniovy věty, jestli má vůbec smysl jí řešit, najít si hodnosti (matice soustavy, rozšířené).

3. Určete všechny dvojice přirozených čísel c, d, pro které platí:

| 4 c 0  |
| 1 2 1  | = 0
| 0 d -3 |

Diskriminant je nula (omlouvám se, ale nenašel jsem v LaTeXu maticovou reprezentaci).
No, Sarrusovo pravidlo mi asi moc nepomohlo, vyjádřil jsem si c a d, ale nejspíš bych potřeboval najít nějakou další rovnici.
První rovnici jsem našel dle SP: 4d - 3c + 24 = 0
Pak tu jsou vlastnosti, kdy je determinant jednoznačně roven nule, a to, že jeden řádek je lin. kombinací ostatních řádků... ale nějak s tím nehnu. (Jiná a chytřejší domněnka?)

4. Rovinný graf, Eulerovský graf
http://forum.matweb.cz/upload3/img/2012-06/39344_eulor.png
Rovinný nejspíš není, kříží se hrany, které se křížit dle poučky nesmí. A Eulerovský nevím, nehledal jsem extra.

5. Matice sousednosti
http://forum.matweb.cz/upload3/img/2012-06/39488_maticesous.png

Kreslit graf se nemá, OK.
Vím, jak to logicky zjistit, u toho souvislého grafu jde o to, že vždy musí platit [a, b] - [b, a], z té matice sousednosti je to potom viditelné ze souměrnosti dle hlavní diagonály (nespíš). Požadován je algoritmus, jak na to?

Díky za dodatky, potřebuju si pár věcí kolem grafů srovnat a uvědomit... spěchá! :-) Nejde o žádné domácí úkoly, jsou to různorodá zadání na magisterském studiu v přijímacím řízení.


Srdcem trochu-programátor, duší rádoby-matematik a povoláním analytik-vývojář.

Offline

 

#2 17. 06. 2012 16:13 — Editoval OiBobik (17. 06. 2012 16:16)

OiBobik
Moderátor
Místo: Brno/Praha
Příspěvky: 1013
Škola: MFF UK Mat. struktury
Pozice: student
Reputace:   82 
 

Re: smíšené příklady

↑ RePRO:

ahoj,

1) Počet hran úplného grafu je počet všech (neuspořádaných u neorientovaného grafu) dvojic vrcholů - mezi každou dvojicí vede právě jedna hrana.
Každý úplný podgraf K4 úplného grafu je jednoznačně dán množinou svých vrcholů. Jde tedy o to, spočítat čtyřprvkové podmnožiny vrcholů grafu.

2) rovnice si nemůžeš jen tak odmýšlet, příklad:

x+y=0
2x+2y=0
x+3y=0

není ekvivalentní

x+y=0
2x+2y=0

Tu přebytečnou rovnici zkrátka vyeliminuješ z těch předchozích.

při větším počtu neznámých, než rovnic, ti vyjde (v homogenním případě) jako řešení podprostor (třeba přímka). Popíšu jej tak, že s přebytečnými proměnnými pracuju jako s parametrem. viz třeba skripta pana Olšáka, hned ze začátku povídá o soustavách rovnic.

3. Rovnici máš sestavenou dobře, není potřeba žádné další. Řešení je nekonečně mnoho, situace je stejná, jako v tvém dotazu 2. druhá část.

4. Graf rovinný je (to, že není rovinně nakreslený, neznamená, že není rovinný), Eulerovský nebude (jaké je kritérium, aby graf byl eulerovský?).

5. To, co popisuješ, je konstatování, že graf je neorientovaný. Aby byl souvislý, musí mezi každými dvěma vrcholy vést cesta (posloupnost navazujících hran).


"The first rule of Tautology Club is the first rule of Tautology Club." [xkcd]

Offline

 

#3 17. 06. 2012 19:59

RePRO
Místo: Jihlava
Příspěvky: 363
Škola: AI VŠPJ (09-12, Bc.)
Pozice: programátor
Reputace:   11 
Web
 

Re: smíšené příklady

1) A výpočetně to mám dobře? Mám tedy množinu 4 vrcholů, a z toho chci získat dvouprvkové podmnožiny?
To znamená při V = {1, 2, 3, 4}, hledáme Vx = {[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]}. Ale pak mi variace nevychází V2(4).

2) V tom už mám jasno.

3) OK.

4)

a) Psal jsem, že pokud se hrany kříží, tak nemůže být tento graf rovinný, je to tak? Možná to vidím špatně.
b) Říkáme, že graf lze nakreslit jedním tahem, jestliže v něm existuje tah obsahující všechny vrcholy a všechny hrany grafu. Graf, který lze nakreslit jedním uzavřeným tahem, se nazývá eulerovský graf. Kdy se graf dá nakreslit jedním tahem? Graf se dá nakreslit jedním tahem, právě když je souvislý a zároveň
- buďto všechny jeho vrcholy mají sudý stupeň (kreslíme uzavřený tah s libovolným počátečním vrcholem, který je pak i vrcholem koncovým),
- anebo právě dva vrcholy mají lichý stupeň (kreslíme otevřený tah, kde počáteční vrchol je jeden z těchto vrcholů, druhý je pak koncový).

5) Souvislý graf je takový (neorientovaný) graf, v němž platí, že pro každé dva vrcholy x, y existuje alespoň jedna cesta z x do y. A to je znatelné z matice (dle mého).

Děkuji.


Srdcem trochu-programátor, duší rádoby-matematik a povoláním analytik-vývojář.

Offline

 

#4 17. 06. 2012 20:20 — Editoval OiBobik (17. 06. 2012 20:20)

OiBobik
Moderátor
Místo: Brno/Praha
Příspěvky: 1013
Škola: MFF UK Mat. struktury
Pozice: student
Reputace:   82 
 

Re: smíšené příklady

↑ RePRO:

1)
Nevím teď, co přesně počítáš (v původním zadání se ptáš na několik věcí).
Počet podgrafů K4 v grafu K5 je ${5 \choose 4}=5$
Počet hran K4 je ${4 \choose 2}=6$
Počet hran K5 je ${5 \choose 2}=10$.


4)
a) Nerozlišuješ mezi rovinným nakreslením grafu a rovinným grafem.
Graf je rovinný, pokud existuje nějaké jeho rovinné nakreslení, tj. nakreslení do roviny takové, že žádné dvě hrany se nekříží.
To, že graf není nakreslen rovinně, neznamená, že není rovinný.

b) Ano, to je přesně ono. takže pohledem na graf je jasné, že není eulerovský, ne?

5)
Ano, to je definice souvislého grafu. Ovšem to, co ty popisuješ jako ověření (tj. symetričnost matice sousednosti) neověřuje souvislost grafu. Ty 1 znamenají hrany. triviální příklad:
graf s maticí sousednosti
$\begin{pmatrix}
0 & 1 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1\\
0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 0\\
\end{pmatrix}$
nebude souvislý, ačkoli je matice symetrická (což bude u všech neorientovaných grafů) - nakresli si ho a uvidíš, že první dva vrcholy tvoří jednu komponentu a zbylé tři druhou.


"The first rule of Tautology Club is the first rule of Tautology Club." [xkcd]

Offline

 

#5 17. 06. 2012 21:15

RePRO
Místo: Jihlava
Příspěvky: 363
Škola: AI VŠPJ (09-12, Bc.)
Pozice: programátor
Reputace:   11 
Web
 

Re: smíšené příklady

1) Už je mi to jasné, jsem to ale... :-(

4) Jo takhle, to znamená, že je rovinný, pokud lze nakreslit rovině, aby se jeho hrany nekřížily, OK. :-)

5) Díky za skvělé vysvětlení, já ověřuju něco, co není pravdou. Ta matice sousednosti vždy bude, jak píšeš symetrická (neorientované grafy). Matice, kterou jsi zvolil příkladem bude mít A-B jako hrany, potom C-E a C-D. Z toho vyplývá? V zadání je, že by se to nemělo kreslit a dle nějakého algoritmu poznat, zda-li bude graf souvislý... :-) A jak si psal, rozdělí se to na dvě komponenty - celky.


Srdcem trochu-programátor, duší rádoby-matematik a povoláním analytik-vývojář.

Offline

 

#6 17. 06. 2012 21:40

OiBobik
Moderátor
Místo: Brno/Praha
Příspěvky: 1013
Škola: MFF UK Mat. struktury
Pozice: student
Reputace:   82 
 

Re: smíšené příklady

↑ RePRO:

Jo no. Nicméně algoritmus na ověření je dost přímočarý (nebude to asi nejoptimálnější algoritmus, ale bude to algoritmus): Využívá toho, že "býti spojen cestou" je v neorientovaném grafu ekvivalence. Stačí tedy ověřit, zda všechny vrcholy jsou spojeny cestou s vrcholem a.

Budu mít třeba frontu na vrcholy plus pole oindexované vrcholy s bitem na hodnoty "daleko"/"blízko"
1) Na začátku označíme všechny vrcholy "daleko"
2) Vrchol A strčíme do fronty.
3) Dokud není prázdná fronta, dělej:
3.1 vytáhni vrchol z fronty
3.2 pokud vytažený vrchol je "blízko", zahoď ho a pokračuj na 3); pokud je "Daleko", označ jej "blízko".
3.3 projdi řádek matice sousednosti příslušný vytaženému vrcholu. Kdykoli narazíš na 1, hoď vrchol, příslušný sloupci, ve kterém je ona 1, do fronty.
3.4 jdi na 3)
4) projdi pole vrcholů; je-li některý vrchol "daleko", pak máš nesouvislý graf. Jsou-li všechny "blízko", máš souvislý graf.

A stejně to jde dělat se zásobníkem. je to vlastně jen BFS, resp. DFS.


"The first rule of Tautology Club is the first rule of Tautology Club." [xkcd]

Offline

 

#7 17. 06. 2012 23:21

RePRO
Místo: Jihlava
Příspěvky: 363
Škola: AI VŠPJ (09-12, Bc.)
Pozice: programátor
Reputace:   11 
Web
 

Re: smíšené příklady

Díky moc.


Srdcem trochu-programátor, duší rádoby-matematik a povoláním analytik-vývojář.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson