Kombinatorikas un grafu teorijas 18. lekcija

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Kas raksturo neorientētu grafu?

Grafā var būt cilpas.

Šķautnes var savienot vienu virsotni vairākkārt.

Šķautnes norāda virzienu.

Šķautnes ir nesakārtoti pāri, kas savieno atšķirīgas virsotnes. (correct)

Kādas ir divas virsotnes, ja tās ir savienotas ar šķautni?

Izolētas virsotnes.

Blakusvirsotnes. (correct)

Cilpas virsotnes.

Neorientētas virsotnes.

Cik šķautņu var būt starp divām virsotnēm orientētā grafikā?

Neierobežots skaits šķautņu.

Divas šķautnes katrā virzienā.

Nekādas šķautnes.

Viena šķautne katrā virzienā. (correct)

Ko sauc par incidentu virsotni attiecībā uz šķautni?

Virsotni, kas ir šīs šķautnes galapunkts. Signup and view all the answers

Kāds ir virsotņu skaits piemēram, kad Ņ = {𝑎, 𝑏, 𝑐, 𝑑}?

Četri. Signup and view all the answers

Kāds ir triviālā grafika raksturojums?

Tas satur vismaz divas virsotnes. Signup and view all the answers

Cik šķautņu skaits ir dotajā piemērā ar virsotņu kopu 𝑉 = 𝑎, 𝑏, 𝑐, 𝑑?

Piecas. Signup and view all the answers

Kāds ir grafa pamatjēdziens, kas attiecas uz savienojumiem starp virsotnēm?

Šķautne Signup and view all the answers

Ko nozīmē grafu izomorfisms?

Grafu strukturāla līdzība Signup and view all the answers

Kāda ir Eilera formula grafu teorijā?

Virsotņu skaits mīnuss šķautņu skaits vienāds ar 2. Signup and view all the answers

Kas ir Eilera cikls grafikā?

Cikls, kas iet cauri katrai šķautnei tieši vienu reizi. Signup and view all the answers

Kura no šīm teorēmām attiecas uz planāriem grafiem?

Kuratovska-Pontrjagina teorēma Signup and view all the answers

Kāds ir kosmiskajā grafā attēlots maršruts no Zemes uz Marsu?

Zeme – Merkurs, Merkurs – Venēra, Venēra – Marss Signup and view all the answers

Kura grafu teorijas īpašība nodrošina, ka katra virsotne savieno konkrētu skaitu šķautņu?

Virsotnes pakāpe Signup and view all the answers

Kāds ir galvenais atšķirības punkts starp vienkāršu neorientētu grafu un orientētu grafu?

Orientētā grafikā šķautnēm ir noteikta virziens. Signup and view all the answers

Ko sauc par izomorfismu grafā?

Bijektīvu atbilstību starp virsotnēm. Signup and view all the answers

Kā nosaka virsotnes pakāpi grafā?

Kā incidento šķautņu skaitu. Signup and view all the answers

Kāda ir galvenā iezīme, lai noteiktu, vai divi grafi ir izomorfi?

Salīdzināt virsotņu pakāpes. Signup and view all the answers

Kāda ir pozitīvā puspakāpe virsotnei grafā?

Ieejošo šķautņu skaits. Signup and view all the answers

Kas ir apakšgrafi grafā?

Grafu ar virsotņu un šķautņu daudzumu, kas ir mazāks par oriģinālo grafu. Signup and view all the answers

Kā var noteikt, vai divi grafi ir izomorfi, neizmantojot virsotņu skaitu?

Pārbaudot cilpu skaitu katrā grafikā. Signup and view all the answers

Kāds ir vizuālais rādītājs, ka divi grafi varētu būt izomorfi?

Ja ir vienāds virsotņu un šķautņu skaits. Signup and view all the answers

Kas ir spriedums, ja divi grafi nav izomorfi?

Viņiem ir atšķirīgas pakāpes. Signup and view all the answers

Study Notes

Kombinatorikas un grafu teorijas elementi - 18. lekcija

Kombinatorikas un grafu teorijas elementi ir 18. lekcijas tēma.
Kursa saturs ietver kombinatoriskās struktūras, kārtošanas un meklēšanas algoritmus, matemātiskās spēles un grafu teorijas elementus.
Grafu teorijas elementi ietver grafa jēdzienu un pamatdefinīcijas, grafu izomorfismu, elementāru lemmu par rokasspiedieniem, maršrutiem, grafu savienojumu, kokiem, cikliem, Eilera ciklu un ķēdēm, divdaļīgiem grafiem, pilniem grafiem, planāriem grafiem, Eilera formulu, turnīriem, Grinberga teorēmu, Kuratovska-Pontrjagina teorēmu, četru krāsu problēmu un interpretāciju ar grafu palīdzību.
Studentiem kreditpunktu iegūšanai jāveic darbi kombinatorikas elementiem (20%), kārtošanas un meklēšanas algoritmiem, matemātiskajām spēlēm (kas kopā veido 20%), grafu teorijas elementiem (20%) un jāizdod eksāmens (40%).
Kosmisko sakaru piemērs starp planētām ir dots.
Grafa jēdziens un pamatdefinīcijas ir lekcijas temats.
Grafs ir virsotņu un šķautņu kopa.
Virsotnes ir jēdzieni, šķautnes ir saiknes.
Šķautnes var krustoties arī citos punktos, kas nav grafa virsotnes.
Virsotnes v1 un v2 sauc par šķautnes {V1, V2} galapunktiem.
Ja virsotne v ir šķautnes e galapunkts, tad saka, ka e ir incidenta v un v ir incidenta e.
Divas virsotnes sauc par blakusvirsotnēm, ja tās ir savienotas ar šķautni.
Divas šķautnes sauc par blakusšķautnēm, ja tām ir kopīgs galapunkts.
Grafa šķautnes var būt sakārtoti virsotņu pāri, ko sauc par orientētām šķautnēm.
Grafu izomorfisms ir bijektīva atbilstība starp grafa virsotnēm, kas saglabā blakuskaitu.
Lai pārbaudītu, vai divi grafi ir izomorfi, var salīdzināt virsotņu un šķautņu skaitu, cilpas, multišķautnes, virsotņu pakāpes (maksimālā, minimālā), orientētos grafos vērsumu, apakšgrafus (fiksētas garuma ciklus, ķēdes).
Par virsotnes v pakāpi sauc šķautņu skaitu, kas incidentas virsotnei v (cilpas ieskaitot divreiz).

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Šajā 18. lekcijā tiek apskatīti kombinatorikas un grafu teorijas pamati. Tematā iekļautas kombinatoriskās struktūras, kārtošanas un meklēšanas algoritmi, kā arī grafu teorijas elementi un pamatdefinīcijas. Lekcijā tiek piedāvāti piemēri un izaicinājumi studentiem, lai nostiprinātu iegūtās zināšanas.