Teorija grafova

Uvod i motivacija

Königsberški mostovi

Osnovni pojmovi i definicije

Šetnje i povezanost

Još neke vrste grafova

• bipartitan ako se skup vrhova može razdijeliti u dva podskupa $A, B$ takve da svaki brid povezuje jedan vrh iz $A$ i jedan vrh iz $B$

• Eulerov ako u njemu postoji Eulerova tura.

1. Jednostavan graf s $n$ vrhova je povezan ako ima više od ${n-1}\choose 2$ bridova.
2. Graf je bipartitan ako i samo ako nema ciklusa neparne duljine.
3. Multigraf bez izoliranih vrhova ima nezatvorenu Eulerovu stazu ako i samo ako je povezan i ima točno dva vrha neparnog stupnja.
4. Multigraf bez izoliranih vrhova je Eulerov ako i samo ako je povezan i svi su mu vrhovi parnog stupnja.

Zadatci

• Svaki natjecatelj poznaje najviše $n$ ostalih natjecatelja.
• Za svaki prirodni broj $m$ takav da je $1 \leq m \leq n$ postoji barem jedan natjecatelj koji poznaje točno $m$ ostalih natjecatelja.

Literatura

1. Dragana Biljuš – Teorija grafova i zadatci s natjecanja (diplomski rad)
2. Lucija Relić – Teorija grafova (MNM predavanje)
3. Vedran Krčadinac – skripta za kolegij Kombinatorika, PMF-MO
4. Kristina Škreb – Teorija grafova
5. Predavanja iz kolegija “Diskretna matematika” – PMF-MO
6. Proof by Contradiction Using Hall’s Marriage Theorem (Playing Cards) – Mathispowerful4u
7. Vježbe iz kolegija “Diskretna matematika” – PMF-MO
8. Zadatci s natjecanja

---