Teoria graficelor
În matematică , informatică și, mai ales, geometrie combinatorie , teoria graficelor este disciplina care se ocupă cu studiul graficelor , obiectelor discrete care vă permit să schematizați o mare varietate de situații și procese și, adesea, să permiteți analiza în termeni cantitativi și algoritmic .
Istorie
Primul text care ia în considerare graficele ca entități matematice este publicația lui Euler pe „Șapte poduri din Königsberg”. Acest text reprezintă, de asemenea, prima dată când se abordează o problemă de geometrie topologică , care nu depinde de nicio măsurătoare: problema podurilor Königsberg .
În secolul al XIX-lea a fost pusă și discutată problema celor patru culori , care s-a dovedit a fi foarte provocatoare și rezolvată abia în a doua jumătate a secolului al XX-lea . A fost introdusă și problema căilor hamiltoniene . Până la mijlocul secolului al XX-lea nu s-a descoperit nimic altceva.
În a doua jumătate a secolului al XX-lea , studiile și rezultatele s-au dezvoltat pe scară largă, în ton cu evoluțiile puternice în combinatorică și calcul automat. Introducerea computerului a permis, pe de o parte, dezvoltarea investigațiilor experimentale pe grafice (cum ar fi, în special, în demonstrarea teoremei celor patru culori ) și, pe de altă parte, a necesitat teoria graficelor pentru a investiga algoritmi și modele de impact puternic.aplicare. În decurs de cincizeci de ani, teoria graficelor a devenit un capitol extrem de dezvoltat al matematicii, bogat în rezultate profunde și cu puternice influențe aplicative.
Reprezentare
În termeni informali, prin grafic înțelegem o structură formată din: [1]
- obiecte simple , numite vârfuri sau noduri ;
- conexiuni între vârfuri; astfel de legături pot fi:
- neorientate (care sunt dotate cu o direcție, dar nu sunt înzestrate cu o direcție): în acest caz ele se numesc margini , iar graficul este numit „nedirecționat”;
- orientate (adică cu o direcție și o direcție): în acest caz se numesc arce sau căi, iar graficul se numește „orientat” sau digraf ;
- orice date asociate cu noduri și / sau linkuri ; un grafic ponderat este un exemplu de grafic în care fiecare legătură este asociată cu o valoare numerică, numită „greutate”.
Un grafic este reprezentat în general pe plan de puncte sau cercuri, care reprezintă nodurile; conexiunile dintre vârfuri sunt reprezentate de segmente sau curbe care leagă două noduri; în cazul unui grafic direcționat, direcția arcurilor este indicată de o săgeată.
Exemplu de grafic direcționat
Exemplu de grafic ponderat
Poziționarea nodurilor și forma arcurilor sau marginilor este irelevantă, deoarece contează doar nodurile și relațiile dintre ele. Cu alte cuvinte, același grafic poate fi desenat în multe moduri diferite, fără a-i modifica proprietățile.
Pentru un studiu aprofundat al terminologiei specifice teoriei graficelor, puteți consulta glosarul teoriei graficelor .
Aplicații
Structurile care pot fi reprezentate prin grafice sunt prezente în multe discipline, iar multe probleme de interes practic pot fi formulate ca întrebări legate de grafice. În special, rețelele pot fi descrise sub formă de grafice. De exemplu, structura legăturilor din Wikipedia , la fel ca toate hipertextele , poate fi reprezentată printr-un grafic orientat, unde vârfurile sunt articolele, iar arcele reprezintă existența unei legături de la un articol la altul.
Graficele direcționate sunt, de asemenea, utilizate pentru a reprezenta mașini cu stare finită și multe alte formalisme, cum ar fi diagramele de flux , lanțurile Markov , schemele entitate-relație și rețelele Petri .
Dezvoltarea algoritmilor de manipulare a graficelor este unul dintre domeniile de cel mai mare interes în informatică .
Notă
Bibliografie
- ( EN ) K. Thulasiraman, MNS Swamy (1992): Grafice: Teorie și algoritmi , J.Wiley
- ( EN ) Béla Bollobás (1998): Modern Graph Theory , Springer, ISBN 0-387-98488-7
- (EN) Lowell W. Beineke , Robin J. Wilson , Peter J. Cameron , eds (2004): Topics in Algebraic Graph Theory, Cambridge University Press
- ( EN ) D. Cvetković, P. Rowlison, S. Simić (1997): Eigenspaces of Graphs , Cambridge University Press *
- (EN) Diestel Reinhard (2005): Teoria graficelor, ediția a III-a, Springer, ISBN 3-540-26182-6 . De asemenea, disponibil gratuit în format PDF
Elemente conexe
- 05Cxx : inițialele secțiunii MSC dedicate teoriei graficelor.
- Arborele (grafic)
- Calcul combinatorial
- Complexitatea computațională
- Optimizare combinatorie
- Automat cu stare finită
- Gramatica formală
- Limbi Lindenmayer
- Teoria jocului
- Teoria lumii mici
- Organigrama
- Schema de organizare
- Rețea (matematică)
- Arborele genealogic
- Schema de clasificare
- Problema podurilor Königsberg
- Problema poștașului chinez
- Șase grade de separare
- Teoria chimică a graficelor
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere despre teoria graficelor
linkuri externe
- ( EN ) Teoria graficelor , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.
| Controlul autorității | Tesauro BNCF 57127 · LCCN (EN) sh85056471 · GND (DE) 4113782-6 · BNF (FR) cb119384413 (dată) · NDL (EN, JA) 00.562.641 |
|---|
