A grafikonelmélet elemei - PDF ingyenes letöltés

A gráfelmélet elemei

grafikonelmélet

Springer Párizs Berlin Heidelberg New York Hong Kong London Milánó Tokió

Alain Bretto, Alain Faisant, François Hennecart A gráfelmélet elemei

x A gráfelmélet elemei Az utolsó fejezet nem használ nagyon mély eszközöket, de a kezelt fogalmak és a bemutatott eredmények meglehetősen elvontak. Ezért csak második olvasatra ajánlott. A klasszikus szövegek rövid listája grafikonokon található a könyv végén. A kényelem kedvéért a lábjegyzetben megemlítettük az előadásban használt néhány hivatkozást. Caen, Saint-Étienne, 2011. július 26, Alain Bretto, Alain Faisant, François Hennecart.

Próbáljon papíron ábrázolni ezen összefonódó cselekmények struktúráját úgy, hogy az egyes karaktereket térben és időben egyaránt mozgó pontként jeleníti meg. Így olyan grafikonokat fog kapni (abban az értelemben, ahogyan Koenigs és Claude Berge matematikusok adják ezt a kifejezést), amelyek meglehetősen összehasonlíthatók a vasúttársaságok irodáiban használt diagramokkal, és ezt könnyű lesz ellenőriznie, miközben nagyon szoros, soha nem jelentenek ellentmondást, és soha nem okozhatnak kisiklást vagy ütközést. " François Le Lionnais (Paul Féval, Les Bouquins, t. 2. című regényének előszava). Köszönetnyilvánítás A szerzők szeretettel szeretnék köszönetet mondani mindazoknak, akik segítettek nekik a könyv elkészítésében, különösképpen Thierry Charnois-nak (a Caeni Egyetem oktatója), François Foucault-nak (a Saint-Étienne-i Egyetem oktatója), Alkis Grecos-nak (a az Université Libre de Bruxelles), Georges Grekos (a Saint-Étienne-i Egyetem oktatója), Jean-Marie Lebars (a Caeni Egyetem oktatója), Éric Reyssat (a Caeni Egyetem professzora), Philippe Toffin (a Caeni Egyetem).

Tartalom Előszó A szerzőkről vii xiii 1 Alapfogalmak 1 1.1 Irányítatlan grafikonok. 1 1.1.1 fokozat. 6 1.1.2 Lánc és ciklus. 7 1.1.3 Részgráfok. 9 1.2 Kapcsolódó bomlás. 13 1.3 Irányított grafikonok. 14 1.4 Egyszerű grafikonok. 17 1.5 Műveletek grafikonokon. 20 1.6 Grafikonok algoritmikus ábrázolása. 20 1.7 Algoritmusok és komplexitáselmélet. 22 1.7.1 Algoritmus. 22 1.7.2 Egy algoritmus időbeli összetettsége. 24 1.7.3 Komplexitás osztályok. 25 1.8 Grafikon meghatározása az incidenciafüggvényből 26 1.9 Grafikonok izomorfizmusai. Automorfizmusok csoportjai 27 1.10 Kiegészítések: néhány alapvető struktúra. 32 2 Néhány figyelemre méltó grafikon 35 2.1 Kétoldalas grafikonok. 35 2.2 Fák és fák. 39 2.2.1 Fák. 39 2.2.2 Fák. 45 2.3 Ábra nélküli áramkörök. 48 2.4 Euleri- és Hamilton-grafikonok. 50