LV.AMO.2011.5.4,
2.2.1. Matemātisku objektu interpretācijas ar grafiem
MathObjectsAsGraphs: Bināru attiecību, svēršanas uzdevumu vai turnīru attēlošana ar grafiem.
2.2.2. Uzdevumi par virsotnes pakāpi jeb kārtu.
GraphVertexDegree: Apgalvojums: Katrā grafā ir divas virsotnes ar vienādu kārtu. :
LV.AMO.2003.6.4,
2.2.2.1. Virsotne ar maksimālo kārtu
GraphVertexMaxDegree: Apgalvojumi, kuros izvēlas virsotni ar lielāko kārtu, lai iegūtu novērtējumus.
2.2.2.2. Rokasspiedienu lemma
HandshakingLemma: Visu grafa virsotņu kārtu summa ir \(2|E|\), kur \(E\) apzīmē visu šķautņu kopu. :
LV.AMO.2019.8.4,
2.2.2.3. Teorēma par to, ka eksistē apakšgrafs ar noteiktu minimālo virsotnes kārtu
DegreesInSubgraphs: Katrs grafs \(G\), kurā vidējā virsotnes kārta ir vismaz \(d\), satur apakšgrafu, kurā minimālā virsotnes kārta ir vismaz \(\lfloor d/2 \rfloor\).
2.2.3. Orientēti grafi
DirectedGraphs: Orientēti grafi (grafa šķautnēm ir noteikts virziens, ko apzīmē, piemēram, ar bultiņu). :
LV.AMO.2024.8.3,
2.2.3.1. Binārās attiecības
BinaryRelations: Starp vienas kopas elementu pāriem definētās attiecības
2.2.3.1.1. Bināro attiecību refleksivitāte
2.2.3.1.2. Bināro attiecību simetrija
2.2.3.1.3. Bināro attiecību transitivitāte
2.2.3.1.4. Pilna sakārtojuma attiecības :
LV.AMO.2017.9.4,
LV.AMO.2018.9.4,
2.2.4. Ceļi un cikli grafos
PathsAndCyclesInGraphs: Ceļš kā savstarpēji savienojamu šķautņu virkne. Vienkāršs ceļš - tāds, kurā nekādām divām šķautnēm nav kopīgu virsotņu (izņemot tās virsotnes, kur viena šķautne virknē savienota ar nākamo šķautni).
2.2.4.1. Eilera cikla eksistence
EulerCircuits: Eilera cikls grafā iespējams tad un tikai tad, ja grafs ir sakarīgs un tajā katras virsotnes kārta ir pāra skaitlis. (Eilera ceļš, kuram nav jābeidzas tajā pašā punktā, kur tas sācies, pietiek, lai visu, izņemot divu virsotņu kārtas ir pāra skaitļi.)
2.2.4.2. Hamiltona cikla eksistence
HamiltonCircuits: Daži Hamiltona cikla nepieciešamie nosacījumi. :
LV.AMO.2007.7.1,
LV.AMO.2022B.8.4,
LV.AMO.2022B.9.4,
2.2.4.3. Grafa šķautņu sadalīšana ciklos
GraphDecompositionInCircuits: Grafa šķautņu nokrāsošana vairākās krāsās tā, lai katra krāsa veidotu ciklu.
2.2.4.4. Divdaļīgi (bipartite) grafi
BipartiteGraphsCycles: Divdaļīgo grafu nepieciešamais un pietiekamais nosacījums - grafā nav ciklu ar nepāra garumu.
2.2.4.5. Uzdevumi par pieaudzēšanu ar ierobežojumiem
GraphAugmentationWithRestrictions: Kāds ir mazākais skaits šķautņu, kas jāpievieno grafam, lai tas kļūtu sakarīgs (vai k-connected - katras divas virsotnes savienotas ar k ceļiem bez kopīgām virsotnēm) vai tajā rastos Eilera cikls. Arī otrādi - kāds mazākais skaits šķautņu, kas jāpārgriež, lai grafā nebūtu nepāra ciklu, lai tas kļūtu divdaļīgs.
2.2.5. Sakarīgi grafi un dalīšana sakarīgās komponentēs
GraphConnectivity: Sakarīgs grafs (*connected graph*), kurā starp katrām divām virsotnēm ir ceļš.
2.2.6. Apakšgrafi
Subgraphs: Virsotņu vai šķautņu izmešana no grafiem un grafu dalīšana gabalos :
LV.AMO.2014.8.3,
2.2.7. Koki
Trees: Apgalvojumi par neorientētiem kokiem bez definētas saknes. Sakarīgs grafs bez cikliem satur tieši \(m=n-1\) šķautnes (par vienu šķautni mazāk nekā virsotņu). Kokā pārgriežot jebkuru šķautni, rodas divi komponenti (kas arī ir koki, ja vientuļu virsotni arī uzskatām par "koku").
2.2.8. Grafu apstaigāšana
GraphTraversal: DFS (*Depth first search* jeb apstaigāšana dziļumā), BFS (*Breadth first search* jeb apstaigāšana platumā), koku un patvaļīgu grafu apstaigāšana.
2.2.9. Planārie grafi
PlanarGraphs: Grafi, kurus var attēlot plaknē bez šķautņu krustošanās.
2.2.9.1. Planaritātes nosacījumi
GraphPlanarityConditions: Grafa planaritātes nosacījumi. Planārs grafs nesatur \(K_5\) vai \(K_{3,3}\) kā apakšgrafus.
2.2.9.2. Eilera formula un tās secinājumi
EulerFormulaPlanarGraphs: Eilera formula planāriem grafiem: \(E = V+F-2\) un tās sekas
2.2.10. Grafa virsotņu vai šķautņu krāsošana vai apzīmēšana
GraphColoringAndLabeling: Virsotņu vai šķautņu izkrāsošanas uzdevumi. Ramseja teorija. Simbolu virkņu vai svaru pierakstīšana grafa virsotnēm vai šķautnēm. :
LV.AMO.2003.5.4,
2.2.10.1. Grafi ar krāsainām šķautnēm
GraphsWithColoredEdges: Uzdevumi par pazīstamiem/nepazīstamiem cilvēkiem vai citām situācijām, kur pilna grafa šķautnes izkrāsotas vairākās krāsās. Ramseja teorēma. Ramseja skaitļi pilniem grafiem. Piesātināti grafi. Vispārināti Ramseja skaitļi. Ramseja uzdevumi nepilniem grafiem.
2.2.10.2. Grafi ar krāsainām virsotnēm
GraphColoredVertices: Grafu virsotņu krāsošana. Četru krāsu teorēmai līdzīgi rezultāti. :
LV.AMO.2022B.9.5,
LV.AMO.2023.5.4,
LV.AMO.2024.7.3,
LV.NOL.2015.7.3,
2.2.10.2.1. Neatkarīga virsotņu kopa grafā
GraphIndependentSet: Nosacījumi, pie kuriem var atrast grafa virsotņu kopu, kurā nekādas divas virsotnes nav savienotas. :
LV.AMO.2023.7.1,
2.2.10.3. Grafu numerācijas
GraphEnumeration: Grafa virsotņu vai šķautņu numerēšana ar veseliem skaitļiem, ievērojot noteiktus ierobežojumus.
2.2.10.3.1. Graciozie grafi
GracefulLabeling: Gracioza virsotņu numurēšana grafā: Grafā ar \(m\) šķautnēm piešķirt virsotnēm atšķirīgus numurus no \(0\) līdz \(m\) tā, lai katras šķautnes galapunktu numuru starpības būtu dažādas pēc absolūtās vērtības un pieņemtu visas vērtības no \([1;m]\).
2.2.10.3.2. Maģiskie grafi
MagicGraphs: Grafi, kuru šķautnes var sanumurēt ar naturāliem skaitļliem no \(1\) līdz \(m\) tā, lai katrai virsotnei pievienoto šķautņu numuru summa būtu viena un tā pati.
2.2.10.4. Minimaksa teorēmas
MinMaxTheorems: Vairākas teorēmas par optimālām konfigurācijām grafos.
2.2.10.4.1. Holla teorēma
HallMarriageTheorem: Holla teorēma par nepieciešamo un pietiekamo nosacījumu, lai divdaļīgā grafā eksistētu maksimālais sapārojums.
2.2.10.4.2. Dilvorsa lemma un Dilvorsa teorēma
DilworthLemmaAndTheorem: Ja daļēji sakārtota kopa satur \(m \cdot n + 1\) elementus, tad tajā var atrast
vai nu ķēdi, kuras garums ir \(m + 1\), vai antiķēdi, kuras garums ir \(n + 1\) (un citi radniecīgi rezultāti).
2.2.10.4.3. Kēniga teorēma
KonigTheorem: Kőnig-a teorēma par grafu maksimāliem sapārojumiem: Katrā divdaļu grafā šķautņu skaits maksimālā sapārojumā ir vienāds ar virsotņu skaitu minimālajā virsotņu pārklājumā.
2.2.10.4.4. Erdeša-Šekereša teorēma
ErdosSzekeresTheorem: Naturāliem skaitļiem \(r\), \(s\) un katrai virknei ar vismaz \((r − 1)(s − 1) + 1\) reāliem skaitļiem ir vai nu monotoni augoša apakšvirkne garumā \(r\), vai arī monotoni dilstoša apakšvirkne garumā \(s\).
2.2.10.5. Vidējā vērtība bezgalīgiem grafiem
MeanValueInGraphAnalysis: Vidējā vērtība un citu novērtējumu izmantošana, apskatot bezgalīgus grafus.