Elemente de teorie a graficelor - Descărcare gratuită PDF
Elemente ale teoriei graficelor
Springer Paris Berlin Heidelberg New York Hong Kong Londra Milano Tokyo
Alain Bretto, Alain Faisant, François Hennecart Elemente ale teoriei graficelor
x Elemente ale teoriei graficelor Ultimul capitol nu folosește instrumente foarte profunde, dar conceptele tratate și rezultatele demonstrate sunt destul de abstracte. Prin urmare, este recomandat doar pentru a doua lectură. O scurtă listă de texte clasice pe grafice poate fi găsită la sfârșitul cărții. Pentru comoditate, am menționat în nota de subsol câteva referințe utilizate în prezentare. Caen, Saint-Étienne 26 iulie 2011, Alain Bretto, Alain Faisant, François Hennecart.
Încercați să reprezentați pe hârtie structurile acestor comploturi împletite arătând fiecărui personaj un punct care se mișcă atât în spațiu cât și în timp. Veți obține astfel grafice (în sensul pe care îl dau matematicienii Koenigs și Claude Berge acestui termen) destul de comparabile cu cele utilizate în birourile companiilor feroviare și vă va fi ușor să verificați acest lucru, în timp ce sunteți foarte strânse, ele nu implică niciodată contradicție și nu ar putea provoca niciodată deraieri sau coliziuni. " François Le Lionnais (prefață a romanului Les habits noirs de Paul Féval, col. Bouquins, t.2). Mulțumiri Autorii doresc să le mulțumească cu căldură tuturor celor care i-au ajutat la pregătirea acestei cărți și în special Thierry Charnois (lector la Universitatea din Caen), François Foucault (lector la Universitatea din Saint-Étienne), Alkis Grecos (profesor la Universitatea Libre de Bruxelles), Georges Grekos (lector la Universitatea din Saint-Étienne), Jean-Marie Lebars (lector la Universitatea din Caen), Éric Reyssat (profesor la Universitatea din Caen), Philippe Toffin (lector la Universitatea din Caen).
Cuprins Cuvânt înainte Cuvinte despre autori vii xiii 1 Concepte fundamentale 1 1.1 Grafice nedirecționate. 1 1.1.1 Grad. 6 1.1.2 Lanț și ciclu. 7 1.1.3 Subgrafe. 9 1.2 Descompunerea aferentă. 13 1.3 Grafice direcționate. 14 1.4 Grafice simple. 17 1.5 Operații pe grafice. 20 1.6 Reprezentări algoritmice ale graficelor. 20 1.7 Algoritmi și teoria complexității. 22 1.7.1 Algoritm. 22 1.7.2 Complexitatea timpului unui algoritm. 24 1.7.3 Clase de complexitate. 25 1.8 Definiția unui grafic din funcția de incidență 26 1.9 Izomorfisme ale graficelor. Grupuri de automorfisme 27 1.10 Complimente: unele structuri de bază. 32 2 Câteva grafice remarcabile 35 2.1 Grafice bipartite. 35 2.2 Copaci și copaci. 39 2.2.1 Copaci. 39 2.2.2 Copaci. 45 2.3 Digrame fără circuit. 48 2.4 Grafele euleriană și hamiltoniană. 50