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 20. 02. 2023 20:45

betamecek
Zelenáč
Příspěvky: 4
Škola: PŘF UPOL
Pozice: student, učitel na základní škole
Reputace:   
 

Teorie grafů - r-regulární graf (r-pravidelný graf)

Zdravím všechny

Potřeboval bych pomoci s příkladem níže. Myslel jsem si že už jsem ho vyřešil, ale řešení mi bylo vráceno.

Zadání: Určete všechny dvojice přirozených čísel (r,n) takových, že existuje r-regulární graf na n vrcholech.

Moje řešení bylo že součin r a n musí být sudý (podle principu sudosti) a podmínka r <= n-1 (stupeň vrcholů nemůže být větší než počet vrcholů mínus jedna)

Vedoucí předmětu mi na to napsal tohle:  Bude existovat regularny graf napr. pre r=17 a n=64? Co ak taky graf neexistuje. Je potrebne popisat pre dane r,n ako sa najde prislusny regularny graf.

Něco mi uniká a já nejsem schopný to dořešit.

Děkuji předem za jakékoliv nápady :)

Betamecek

Offline

 

#2 20. 02. 2023 23:47

check_drummer
Příspěvky: 4677
Reputace:   102 
 

Re: Teorie grafů - r-regulární graf (r-pravidelný graf)

↑ betamecek:
Ahoj, a co ti není jasné? Zda ten graf pro r=17 a n=64 existuje?
Podle mě není potřeba tu konstrukci popsat, ale stačí dokázat, že ten graf existuje.
Co jsi ukázal ty jsou nutné podmínky, ale není jasné, zda jsou postačující. To můžeš dokázat konstrukcí, ale i jinak.


"Máte úhel beta." "No to nemám."

Offline

 

#3 21. 02. 2023 11:09

betamecek
Zelenáč
Příspěvky: 4
Škola: PŘF UPOL
Pozice: student, učitel na základní škole
Reputace:   
 

Re: Teorie grafů - r-regulární graf (r-pravidelný graf)

Jasný mi není ten poslední požadavek. Ten graf by existovat měl, podle mých podmínek, ale nevím jak popsat pro dané r,n, jak se najde příslušný regulární graf. Výpočet hran pro regulární graf jsem v řešení měl, na základě toho jsem aplikoval princip sudosti. Tak nevím, jak dál popsat hledání příslušného grafu.

Děkuji předem za odpověď :)

Offline

 

#4 21. 02. 2023 17:54

Stýv
Vrchní cenzor
Příspěvky: 5692
Reputace:   215 
Web
 

Re: Teorie grafů - r-regulární graf (r-pravidelný graf)

betamecek napsal(a):

Ten graf by existovat měl, podle mých podmínek

To prave z tech tvych podminek nevyplyva, protoze jde o podminky nutne, nikoli postacujici. Resp. nedokazal jsi, ze jsou postacujici.

Offline

 

#5 21. 02. 2023 21:31

betamecek
Zelenáč
Příspěvky: 4
Škola: PŘF UPOL
Pozice: student, učitel na základní škole
Reputace:   
 

Re: Teorie grafů - r-regulární graf (r-pravidelný graf)

↑ Stýv:

A jak teda dokážu, že ty podmínky jsou dostačující? Nějakým konkrétním příkladem?

Děkuji za odpověď.

Omlouvám se za nechápavost, ve tvoření důkazů moc zběhlý nejsem.

Offline

 

#6 22. 02. 2023 01:19

check_drummer
Příspěvky: 4677
Reputace:   102 
 

Re: Teorie grafů - r-regulární graf (r-pravidelný graf)

↑ betamecek:

Máš dvě množiny - množinu A, která obsahuje všechny dvojice přirozených čísel (r,n) takových, že existuje r-regulární graf na n vrcholech.

A tu množinu chceš nějak pěkně popsat - ty jsi zvolil množinu B dvojic (r,n) takových, že součin r a n musí být sudý a r <= n-1,

A teď chceš dokázat, že ty množiny jsou stejné, tj. že A=B. Důkaz rovnosti dvou množin se provádí většinou tak, že dokážeš že platí [mathjax]A \subseteq B[/mathjax] a že platí [mathjax]B \subseteq A[/mathjax].

Ty jsi zatím dokázal první inkluzi, tj. [mathjax]A \subseteq B[/mathjax], tedy že je-li nějaká dvojice v množině A, pak je i v množině B.

Teď je třeba dokázat inkluzi opačnou.

Jedna věc je vědět co chceme dokázat (to bys měl vědět vždy) a druhá věc je jak to dokázat (to je kolikrát těžké).


"Máte úhel beta." "No to nemám."

Offline

 

#7 22. 02. 2023 20:27

Stýv
Vrchní cenzor
Příspěvky: 5692
Reputace:   215 
Web
 

Re: Teorie grafů - r-regulární graf (r-pravidelný graf)

↑ betamecek: Jednou moznosti by bylo dat obecny navod, jak pro libovolne (r,n) splnujici tvoje podminky ten graf sestrojit. Konkretnim prikladem tady nic nedokazes, muze ti ale poslouzit pro predstavu, jak by vypadal ten obecny postup.

Offline

 

#8 22. 02. 2023 22:52

osman
Příspěvky: 210
Pozice: v.v.
Reputace:   
 

Re: Teorie grafů - r-regulární graf (r-pravidelný graf)

↑ betamecek:
Ahoj, zkusil bych si vzít úplný graf, který je samozřejmě regulární, a zformulovat obecný způsob mazání hran vedoucí k regulárnímu grafu s menším r.


Hlavní je zápal, talent se dostaví!

Offline

 

#9 23. 02. 2023 10:23

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1012
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teorie grafů - r-regulární graf (r-pravidelný graf)

Konkrétní řešení hodně závisí na to, co máte v předmětu probráno.
Pár tipů: konstrukce nemusí být stejná pro n sudé a pro n liché. Dále může pomoci pojem doplňku grafu (ale není bezpodmínečně potřeba).

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson