SURÁNYI LÁSZLÓ: Gráfelmélet I. fejezet

SURÁNYI LÁSZLÓ: Gráfelmélet I. fejezet

A gráf fogalma, pont, él, fokszám

Két lehetőség van az olvasásra:  

I. lehetőség: a fejezet anyaga három fájlban:

Az egész bevezető (1-16. feladat+ alapfogalmak)

További feladatok (17–40. feladat)

A további feladatok megoldása egy fájlban

II. lehetőség: A bevezető feladatok feldolgozása lépésenként; a további feladatok megoldásai külön-külön olvashatók:  

A) A bevezető feladatok feldolgozása lépésenként

B) További feladatok (minden megoldás külön olvasható)

Tartalomjegyzék – a fogalom definíciója a fogalom nevére kattintva érhető el:

      A gráf fogalmának (a gráf csúcsának, élének, egy pont fokszámának, szomszédainak) bevezetése: I/1–4. feladat

      Az egyszerű gráf fogalmának (a többszörös él, hurokél fogalmának) bevezetése: I/4b feladat–I/5.a feladat

      Izolált pont fogalma: I/5 feladat

      Véges egyszerű gráfban van két azonos fokú pont: I/4b

           Kitérő a végtelen gráfról: I/6

            Kitérő az irányított gráfról: I/7; pont kifoka, befoka

      A komplementer gráf fogalmának bevezése

      A teljes gráf (és üres gráf) fogalmának bevezetése,

       Kn: az n pontú teljes gráf Az n pontú teljes gráf élszáma: I/9

      A reguláris gráf fogalma: I/10

       n pontú, 3-reguláris gráf létezésének szükséges és elégséges feltétele: I/10

      Fokszám és élszám közötti összefüggés:

       Euler-tétel bevezetése:

      I/9, I/10, I/11, I/12,

      többszörös élek esetén: I/12a

      Független ponthalmaz bevezetése: I/14, I/15
            Alternatív definíció: az általa feszített részgráf üres

      Részgráf fogalma

      Feszített részgráf fogalma

      Páros gráf fogalma

      Telített pont fogalma

B) További feladatok (gyakorló és nehezebb feladatok) Témák szerint:

      „Barátság-probléma”: I/27

      Élszám becslés: I/29

      Élszámozási feladat: I/32, I/33

      Euler-tétel: I/19, I/20, I/21, I/29, I/30

      Fokszám: I/17, I/18, I/19, I/39, I/40
            Fokszám és élszám összefüggése: I/20, I/21
            Fokszám paritására vonatkozó feladatok: I/20, I/21, I/22, I/36, I/37
            Fokszám és átlagfokszám összefüggése: I/29, I/30
            Fokszám és közös szomszédok összefüggése: I/25, I/27, I/28

      Irányított gráf: I/23

      Izolált pont: I/41

      Páros gráf: I/22, I/23

      Ramsey-előzetes: I/29

      Reguláris gráf: I/10, I/19, I/27

      Részgráf:
            feszített részgráf: I/34, I/37

            Szabályos testek gráfja:
            Ikozaéder gráfja: I/33d
            Kocka gráfja: I/33c
            Oktaéder gráfja: I/33b
            Tetraéder gráfja: I/33a (pont)

      Szomszédai,
      Közös szomszédok: I/16, I/25, I/26, I/28, I/29

      Telített pont: I/27, I/34, I/41a, I/41b, I/41c, I/41d,

Függelék

      Teljes részgráfok („klikkek”): I/24, I/31

      „Turán-típusú tételek” (előzetes): I/31

      Nevezetes módszerek:

      Állapotfüggvény: I/35

       Kétszeres leszámolás:       Euler-tétel, I/9 , I/21, I/22, I/39

      Logikai szita: I/41d,

Függelék

      Skatulyaelv: I/1, I/36

      „Vegyük a legnagyobbat”: I/39