Kombinatorikas un grafu teorijas 18. lekcija
23 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

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?

<p>Virsotni, kas ir šīs šķautnes galapunkts. (D)</p> Signup and view all the answers

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

<p>Četri. (C)</p> Signup and view all the answers

Kāds ir triviālā grafika raksturojums?

<p>Tas satur vismaz divas virsotnes. (C)</p> Signup and view all the answers

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

<p>Piecas. (A)</p> Signup and view all the answers

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

<p>Šķautne (B)</p> Signup and view all the answers

Ko nozīmē grafu izomorfisms?

<p>Grafu strukturāla līdzība (D)</p> Signup and view all the answers

Kāda ir Eilera formula grafu teorijā?

<p>Virsotņu skaits mīnuss šķautņu skaits vienāds ar 2. (D)</p> Signup and view all the answers

Kas ir Eilera cikls grafikā?

<p>Cikls, kas iet cauri katrai šķautnei tieši vienu reizi. (D)</p> Signup and view all the answers

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

<p>Kuratovska-Pontrjagina teorēma (C)</p> Signup and view all the answers

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

<p>Zeme – Merkurs, Merkurs – Venēra, Venēra – Marss (A)</p> Signup and view all the answers

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

<p>Virsotnes pakāpe (B)</p> 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?

<p>Orientētā grafikā šķautnēm ir noteikta virziens. (D)</p> Signup and view all the answers

Ko sauc par izomorfismu grafā?

<p>Bijektīvu atbilstību starp virsotnēm. (C)</p> Signup and view all the answers

Kā nosaka virsotnes pakāpi grafā?

<p>Kā incidento šķautņu skaitu. (C)</p> Signup and view all the answers

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

<p>Salīdzināt virsotņu pakāpes. (C)</p> Signup and view all the answers

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

<p>Ieejošo šķautņu skaits. (C)</p> Signup and view all the answers

Kas ir apakšgrafi grafā?

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

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

<p>Pārbaudot cilpu skaitu katrā grafikā. (A), Salīdzinot maks. virsotņu pakāpes. (B)</p> Signup and view all the answers

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

<p>Ja ir vienāds virsotņu un šķautņu skaits. (C)</p> Signup and view all the answers

Kas ir spriedums, ja divi grafi nav izomorfi?

<p>Viņiem ir atšķirīgas pakāpes. (D)</p> Signup and view all the answers

Flashcards

Kas ir grafs?

Grafs ir matemātiska struktūra, kas sastāv no virsotnēm un šķautnēm, kas savieno tās. Virsotnes var attēlot objektus, bet šķautnes - to savstarpējās attiecības.

Kas ir izomorfi grafi?

Divi grafi ir izomorfi, ja to virsotnes un šķautnes var savstarpēji atbilst, saglabājot to savstarpējās saiknes. Citiem vārdiem sakot, viens grafs ir vienkārši “pārkrāsots” otra nozīmē.

Kas ir virsotnes pakāpe?

Šķautņu skaits, kas ir incidentas konkrētai virsotnei.

Kas ir pilns grafs?

Grafs, kurā atrodas visi iespējamie savienojumi starp visām virsotnēm.

Signup and view all the flashcards

Kas ir planārs grafs?

Grafs, ko var attēlot plaknes virsmā tā, lai tā šķautnes nekrustotu cita citu.

Signup and view all the flashcards

Kādu grafā izveidot, lai redzētu, vai ar kosmosa kuģi var nokļūt no Zemes uz Marsu?

Izmantotais grafs apraksta sakarus starp planētām, kur virsotnes ir planētas, bet šķautnes ir kosmosa kuģu maršruti. Lai noskaidrotu, vai ir ceļš no vienas planētas uz otru, jāpārbauda, vai starp tām ir savienojums (šķautne) grafā.

Signup and view all the flashcards

Kas ir apakšgrafs?

Apakšgrafs ir grafa daļa, kurā ir iekļautas visas virsotnes un visas šķautnes, kas savieno šīs virsotnes.

Signup and view all the flashcards

Kas ir Lemma par rokasspiedieniem?

Lemma par rokasspiedieniem apgalvo, ka katra grafa visu virsotņu pakāpju summa ir vienāda ar divreiz lielāku par šķautņu skaitu.

Signup and view all the flashcards

Vienkāršs neorientēts grafs

Grafā, kas sastāv no virsotņu kopas (V) un šķautņu kopas (E), kur V ir netukša un galīga, bet E ir V elementu nesakārtoti pāri, kas veido šķautnes, savienojot divas atšķirīgas virsotnes. Šķautnēs nav cilpu, un katrs virsotņu pāris var būt savienots ar ne vairāk kā vienu šķautni.

Signup and view all the flashcards

Virsotņu kopa (V)

Virsotņu kopa grafā. Piemēram, grafā G=(V,E) V apzīmē visu virsotņu kopu.

Signup and view all the flashcards

Šķautņu kopa (E)

Šķautņu kopa grafā. Piemēram, grafā G=(V,E) E apzīmē visu šķautņu kopu.

Signup and view all the flashcards

Galapunkti

Divi grafa punkti, kurus savieno šķautne.

Signup and view all the flashcards

Incidences

Ja virsotne ir uz šķautnes, tad saka, ka virsotne ir incidenta šķautnei, un šķautne ir incidenta virsotnei.

Signup and view all the flashcards

Blakusvirsotnes

Divas virsotnes, kuras savieno viena šķautne.

Signup and view all the flashcards

Blakusšķautnes

Divas šķautnes, kurām ir kopīgs galapunkts.

Signup and view all the flashcards

Vienkāršs orientēts grafs

Grafā, kur šķautnes ir orientētas (ar bultiņām), un katras divas virsotnes var būt savienotas ar ne vairāk kā vienu šķautni katrā virzienā (no A uz B un no B uz A).

Signup and view all the flashcards

Izomorfisms grafiem

Divi grafi 𝐺 un 𝐺′ tiek uzskatīti par izomorfiem, ja ir iespējams pārdēvēt 𝐺 virsotnes tā, lai iegūtu grafu 𝐺′. Citiem vārdiem sakot, ja starp abu grafu virsotnēm ir bijektīva atbilstība, kas saglabā blakusvirsotņu attiecības, tad grafi ir izomorfi.

Signup and view all the flashcards

Virsotnes pakāpe

Virsotnes 𝑣 pakāpe ir šķautņu skaits, kas ir incidentas ar šo virsotni. Katra cilpa tiek skaitīta divas reizes. Šo skaitu apzīmē kā 𝑑(𝑣).

Signup and view all the flashcards

Apakšgrafu definīcija

Oriģinālā grafa apakšgrafu veido virsotņu un šķautņu kopa, kas ir oriģinālā grafa virsotņu un šķautņu kopu apakškopas.

Signup and view all the flashcards

Izomorfismu pārbaude

Lai pārbaudītu, vai divi grafi ir izomorfi, var salīdzināt dažādas īpašības, piemēram, virsotņu un šķautņu skaitu, virsotņu pakāpi, ciklus, apakšgrafus, un vai grafs ir orientēts vai neorientēts.

Signup and view all the flashcards

Pozitīvās un negatīvās puspakāpes

Orientēta grafa virsotnes 𝑣 pozitīvo (negatīvo) puspakāpi apzīmē ar 𝑑+ (𝑣) (attiecīgi 𝑑− (𝑣)). Tas norāda ieejošo (attiecīgi izejošo) šķautņu skaitu, kas ir incidentas ar virsotni 𝑣.

Signup and view all the flashcards

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.

Quiz Team

Related Documents

18. lekcija Kombinatorikas un grafu teorijas elementi PDF

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.

More Like This

Exploring Discrete Optimization: Integer Programming, Graph Theory, and Combinatorial Optimization
10 questions

Exploring Discrete Optimization: Integer Programming, Graph Theory, an...

FavoredHydrangea avatar
FavoredHydrangea
Discrete Mathematics Overview Quiz
12 questions

Discrete Mathematics Overview Quiz

FairTrombone avatar
FairTrombone
Graph Theory Problems
18 questions

Graph Theory Problems

AmicableLesNabis avatar
AmicableLesNabis
Combinatoria y Teoría de Grafos
16 questions

Combinatoria y Teoría de Grafos

SupportedAntigorite4099 avatar
SupportedAntigorite4099
Use Quizgecko on...
Browser
Open
Browser
Browser