Prezentarea unui grafic

Reprezentarea graficelor , sau trasarea graficelor , este o disciplină care se află între teoria graficelor și informatică , care se ocupă cu reprezentarea graficelor în două sau trei dimensiuni. Această activitate este motivată de aplicații importante ale teoriei graficelor, cum ar fi proiectarea circuitelor VLSI , cartografie , bioinformatică , analiza rețelelor sociale . Necesită utilizarea noțiunilor de geometrie și topologie și dezvoltarea algoritmilor și a sistemelor software solicitante.

Teorie

Să luăm în considerare o suprafață S în spațiul tridimensional. În special, S ar putea fi un plan , o sferă sau un tor . În teoria graficelor, reprezentarea unui grafic G pe o suprafață S este o figură desenată pe S în care fiecare nod al lui G este reprezentat de un punct diferit de S (punct-nod) în timp ce fiecare vârf {p, q} al lui G este reprezentată de o curbă tendențial regulată (curbă-margine) care își are capetele în punctele nodului corespunzătoare lui p și q și care nu atinge niciun alt punct nod.

Când suprafața S este un plan vorbim despre o reprezentare plană a graficului .

Se spune că două reprezentări ale unui grafic pe o suprafață sunt echivalente topologic dacă pot fi transformate una în alta prin intermediul unei deformări continue . O astfel de deformare nu poate fi făcută să traverseze o curbă-margine cu un punct-nod.

Printre reprezentările unui grafic le distingem pe cele în care nu există margini intersectate: acestea se numesc reprezentări plane . În special, se disting reprezentările planului plan .

Există grafice care nu au reprezentări plane plane, cum ar fi, de exemplu, graficele lui Kuratowski . Reprezentări plane pot fi obținute pentru fiecare grafic atâta timp cât suprafața de imersiune este complicată: dintr-un punct de vedere intuitiv, este vorba de adăugarea unui număr suficient de mânere pe această suprafață.

Criterii pentru desenarea graficelor

Grafice plane

grafic plan reprezentat cu un desen fără intersecții de arc

Planul este definit ca un grafic care poate fi desenat pe plan, astfel încât conexiunile dintre noduri să poată fi reprezentate de segmente care nu se intersectează. Un desen fără intersecții între arce face graficul foarte ușor de înțeles pentru ochiul uman

Algoritmi

Algoritmi direcționați forțat

Algoritmii direcționați forțat sunt o clasă de algoritmi pentru desenarea graficelor. Un algoritm de acest tip consideră desenul graficului ca un sistem fizic, în care se joacă forțe pe noduri. De exemplu, algoritmul Eades (1984) prezice că există forțe de atracție între nodurile adiacente, așa cum se întâmplă într-un arc. Aceste forțe determină adunarea nodurilor adiacente în proiectarea finală. În același timp, algoritmul Eades ia în considerare forțele respingătoare între nodurile non-adiacente, aceste forțe fac ca doi noduri non-adiacente să tindă să se îndepărteze în proiectarea finală. Energia totală a sistemului fizic va scădea dacă nodurile adiacente sunt apropiate și nodurile neadiacente sunt depărtate. Un design inteligibil și plăcut este legat de un sistem fizic cu energie redusă. ^[1]

Notă

Bibliografie

• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs , Prentice Hall, 1999.
• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis, Algorithms for Drawing Graphs: an Annotated Bibliography , in Computational Geometry: Theory and Applications , 4, pp. 235-282 (1994).
• Isabel F. Cruz, Roberto Tamassia, Tutorial de desen grafic

Elemente conexe

• Grafic plan

linkuri externe

Site-urile web enumerate mai jos sunt deosebit de remarcabile.

• graphdrawing.org , site-ul oficial al „Graph Drawing Steering Committee”, comitetul care organizează anual Simpozionul internațional privind desenarea graficelor . Acesta include o introducere în limba pentru a descrie grafice graphml, exemple de descrieri specifice grafic și link - uri la multe alte resurse de reprezentare grafic.
• Arhiva e-print pentru desen grafic colectează informații despre articolele prezentate la toate simpozioanele Graph Drawing.
• pagina proiectului Open Directory care conține multe alte linkuri referitoare la desenarea graficelor
• site dedicat lui Chisio , un instrument simplu de vizualizare, open-source și de origine academică.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică