Ismerkedés a gráfelmélettel

TARTALOM Előszó 5 Ismerkedés a gráfokkal 9 Alapfogalmak Pontok, élek száma és fokszámok közti kapcsolatok A skatulyaelv Teljes n-gráf élszáma Komplementer gráfokra vonatkozó versenyfeladat Összefüggő gráfok pont-, él- és fokszámai közötti kapcsolatok Utakra és körökre vonatkozó egyszerűbb feladatok Leghosszabb út módszere Összefüggő gráfok két tulajdonsága Gyakorlatok, feladatok Fák és ligetek 26 Kapcsolat a fagráf pontjainak és éleinek száma között Kémiai alkalmazás Fákban levő utak Liget Faváz jellemzése Alapkör, alapkörendszer jellemzése Gráfok ligetváza Gráf rangja és ciklomatikus száma Körmentes hálózat gazdaságos építése; három építési módszer Minimális, ill. maximális értékű faváz keresése Favázak alkalmazása elektormos hálózatok számításaiban Kirschhoff két törvénye Gyakorlatok, feladatok Bejárjuk a gráf éleit 48 A königsbergi hidak problémája Zárt és nyitott gráfok Euler-vonalat, ill. nyitott Euler-vonalat biztosító pontos feltételek Irányított gráfokkal kapcsolatos alapfogalmak Irányított utak, körök, vonalak Közlekedési problémák megfogalmazása irányított gráfokkal Közlekedési feltétel, erősen összefüggő gráf Híd és kör kapcsolata Hidat nem tartalmazó összefüggő gráf irányítható úgy, hogy erősebb összefüggő legyen A maximálisból, ill. minimálisból indulás módszere Euler-vonalat biztosító pontos feltétel irányított gráfokra Egy alkalmazás irányítás nélküli gráfokra Megyjegyzés a végtelen gráfokról Labirintusban Két bejárási utasítás labirintusra Kiállítások folyosórendszereinek bejárása Tetszőlegesen bejárható Euler-gráfok szerkezete Gyakorlatok, feladatok Bejárjuk a gráf pontjait 73 A dodekaéder-játék Hamilton-kör, Hamilton-út Hamilton-kört, ill. -utat kizáró feltétel Alkalmazás sakktáblák bejárására lóugrásokban A dodekaéder-játék teljes elemzése Adott számnál nagyobb hosszúságú kört biztosító fokszámtétel Hamilton-kört, ill. -utat biztosító fokszámfeltételek Hamilton-kör háromszöglapú poliéderekben Irányított Hamilton-kör, ill. -út Irányított teljes gráfnak van Hamilton-útja Irányított Hamilton-kört, ill. -utat biztosító feltételek Megjegyzések végtelen gráfok Hamilton-útjaira Gyakorlatok, feladatok Párosítási gyakorlatok. Faktorok 97 Körmérkőzések szervezése Teljes gráf elsőfokú faktorokra bontása k-adfokú faktorok, reguláris gráfok Független élhalmaz, maximális független élhalmaz Páros fokú reguláris gráf másodfokú faktorokra bontása Teljes gráf Hamilton-körökre bontása Páros gráf Páros gráfok jellemzése Reguláris páros gráf elsőfokú faktorokra bontása Ponthalmazt lefedő élek. A házasítási probléma Alternáló utak módszere Algoritmus páros gráf maximális független élhalmazának keresésére (magyar módszer) Lefogó ponthalmaz, minimális lefogó ponthalmaz Páros gráfokra fémax=lpmin Független ponthalmaz, maximális független ponthalmaz Lefedő élhalmaz, minimális lefedő élhalmaz Izolált pontot nem tartalmazó páros gráfra fpmax=lémin Adott számnál több független élt biztosító fokszámtétel Páros gráfban Hamilton-kört biztosító fokszámtételek Páros gráf elsőfokú faktorát biztosító pontos feltétel Tetszőleges gráf elsőfokú faktorát biztosító pontos feltétel Alkalmazás híd nélküli harmadfokú reguláris gráfokra Faktorokra nem bontható reguláris gráfok Gyakorlatok, feladatok Szélsőértékek. Extrém gráfok 127 Szélsőérték-problémák néhány típusa Néhány elemi kombinatorikai tétel Az n(m, k) Ramsey-féle számok meghatározása három módon A Ramsey-tétel egy speciális esete A Ramsey-féle számok becslése és néhányuk kiszámítása Általánosabb Ramsey-számok Egy Ramsey-típusú szélsőérték-probléma megoldása az irányított kört nem tartalmazó gráfok szerkezetének vizsgálata révén Egy számelméleti alkalmazás Még egy Ramsey-típusú probléma néhány speciális esetének tárgyalása Háromszöget biztosító fokszám- és élszámfeltételek Teljes k-gráfot biztosító élszám- és fokszámtételek Kapcsolat a pontok és élek száma és lpmin között Háromszöget, ill. adott számnál kisebb hosszúságú páratlan kört biztosító fokszám- és élszámfeltételek fpmax különböző korlátozásai és rögzítése mellett Egy gráf tagjának értelmezése Adott számnál nagyobb hosszúságú utat biztosító fokszámfeltétel Adott számnál nagyobb hosszúságú utat, ill. kört biztosító élszámfeltételek Pontfüggetlen köröket biztosító élszámfeltétel Élfüggetlen köröket biztosító élszámfeltétel Gyakorlatok, feladatok A gyakorlatok és feladatok megoldása 181 Irodalmi tájékoztató 227 Irodalomjegyzék 230 Tárgymutató 233