Matematické Fórum

↑ 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).

↑ 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
Počet hran K4 je
Počet hran K5 je .


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

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.

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