Dibuix de grafos

Dibuix de grafos

Representació gràfica d'una fracció de minut de la World Wide Web, mostrant les seues hiperenlaces

El dibuix de grafos és un àrea de les matemàtiques i de les ciències de la computació que combina métodos de la teoria de grafos geomètrica i de visualisació de senyes per a obtindre representacions bidimensionales de grafos que sorgixen d'aplicacions com l'anàlisis de rets socials, la cartografia, la llingüística o la bioinformática.

Un dibuix d'un grafo o diagrama de ret és una representació pictòrica dels vèrtiços i de les conexions d'un grafo. Este dibuix no deu confondre's en el propi grafo: a un mateix grafo poden correspondre dissenys molt diferents. En abstracte, tot lo que importa és qué parells de vèrtiços estan conectats per les arestes. En concret, no obstant, la disposició d'estos vèrtiços i arestes dins d'un dibuix afecta el seu comprensibilidad, usabilidad, cost de fabricació i estètica. El problema empijora si el grafo canvia en el temps agregant i eliminant vores (dibuix dinàmic del grafo) i l'objectiu és preservar el mapa mental de l'usuari.

Convencions gràfiques

Grafo dirigit en puntes de flecha indicant les direccions de fluix

Els grafos es dibuixen en freqüència com a diagrames de nodo-víncul en els que els vèrtiços es representen com a discs, caixes o etiquetes de text i les vores es representen com segments, polilíneas o curves sobre un mig bidimensional. Els diagrames d'enllaç de nodos es remonten a les obres del Pseudo-Lull dels sigles XIV-XVI que es varen publicar en el nom de Ramon Llull, un erudit de el XIII. Pseudo-Lull va dibuixar diagrames d'este tipo per a obtindre un grafo complet en la finalitat d'analisar totes les combinacions per parells entre conjunts de conceptes metafísics.

En el cas dels grafos dirigits, s'utilisen fleches que formen una convenció gràfica d'us comú per a mostrar el seu orientació. No obstant, els estudis d'usuaris han demostrat que atres convencions, com la reducció gradual del tamany dels nodos brinden esta informació de manera més efectiva. En un dibuix pla cap a dalt s'usa la convenció de que cada víncul està orientat des d'un vèrtiç inferior a un vèrtiç superior, lo que fa innecessàries les puntes de flecha.

Les convencions alternatives als diagrames de nodo-enllace inclouen representacions de adyacencia com l'empaquetat de círculs, en les que els vèrtiços estan representats per regions disjuntas en el pla i les vores estan representades per adyacencias entre regions; representacions d'intersecció en les que els vèrtiços estan representats per objectes geomètrics no disjuntos i els vínculs estan representats per les seues interseccions; representacions de visibilitat en les que els vèrtiços estan representats per regions en el pla i els vínculs estan representats per regions que tenen una llínea de visió sense obstrucció entre sí; dibuixos confluentes, en els que els vínculs es representen com a curves suaus dins de vies de tren matemàtiques; teixits, en els que els nodos es representen com a llínees horisontals i els vínculs com a llínees verticals; i visualisacions de la matriu de adyacencia del grafo.

Mides de calitat

S'han definit moltes mides de calitat diferents per als dibuixos grafos, en un intent de trobar mijos objectius per a evaluar la seua estètica i usabilidad. Ademés de guiar l'elecció entre diferents métodos de disseny per al mateix grafo, alguns métodos de disseny intenten optimisar directament estes mides.

Grafo pla dibuixat sense vínculs superposts

El número de creuament d'un dibuix és el número de parells de vínculs que es creuen entre sí. Si el grafo és pla, a sovint és convenient dibuixar-ho sense interseccions de vínculs; és dir, en este cas, el dibuix d'un grafo representa un grafo embebido. No obstant, els grafos no plans sorgixen en freqüència en les aplicacions, per lo que els algoritmes de dibuix de grafos generalment deuen permetre creus de vínculs. l'àrea d'un dibuix és el tamany del seu quadre delimitador més menut, en relació en la menor distància entre dos vèrtiços qualssevol. Els dibuixos en un àrea més chicoteta són generalment preferibles a aquells en un àrea més gran, perque permeten que les característiques del dibuix es mostren en major tamany i, per lo tant, de manera més llegible. El proporció del quadre delimitador també pot ser important. La visualisació de simetria és el problema de trobar un grup de simetria dins d'un grafo donat i trobar un dibuix que mostre la major simetria possible. Alguns métodos de disseny conduïxen automàticament a dibuixos simètrics; alternativament, alguns métodos de dibuix comencen per trobar simetria en el grafo d'entrada per a usar-les en la construcció del dibuix. És important que els vínculs tinguen formes lo més simples possibles, per a que siga més fàcil per a l'ull seguir-los. En els dibuixos en polilíneas, la complexitat d'un víncul es pot medir pel seu número de recodos, i molts métodos apunten a proporcionar dibuixos en pocs quiebros totals o pocs recodos per víncul. De manera similar, per a les curves suavisades, la complexitat d'un víncul pot medir-se pel número de punts de control que requerixen. Vàries mides de calitat comunament utilisades es referixen a la llongitut dels vínculs: generalment és desijable minimisar la seua llongitut total, aixina com la llongitut màxima de qualsevol d'ells. Ademés, pot ser preferible que les seues llongituts siguen uniformes en lloc de molt variades. La resolució angular és una mida dels ànguls més aguts en el dibuix d'un grafo. Si un grafo té vèrtiços de grau alt, necessàriament tindrà una resolució angular menuda, pero la resolució angular pot estar llimitada per una funció del grau.

El número de pendents d'un grafo és el número mínim de pendents d'un víncul distintes necessàries en un dibuix en vínculs de segment de llínea recta (permetent creus). Els grafos cúbics tenen un número de pendents per lo general quatre, pero els grafos de grau cinc poden tindre un número de pendents illimitat; i permaneix obert si el número de pendents dels grafos de grau 4 està acotat.

Vore també

• Anex:Ferramentes del llenguage de modelació unificada

Bibliografia

• .
• .
• .
• .
• (2001).«Drawing Graphs: Methods and Models».Springer-Verlag.2025doi:10.1007/3-540-44969-8..
• (2014).«Handbook of Graph Drawing and Visualization».CRC Press..

Subtemas especialisats

• (2006).«Automata Theory with Modern Applications».Cambridge University Press.

38–41..

• (2014).«Handbook of Graph Drawing and Visualization».CRC Press.

621–651..

• (2001).«Drawing Graphs: Methods and Models».Springer-Verlag.2025

87–120.doi:10.1007/3-540-44969-8_5..

• .
• (2014).«Handbook of Graph Drawing and Visualization».CRC Press.

805–839..

• (2014).«Handbook of Graph Drawing and Visualization».CRC Press.

763–803..

• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• (Enllaç trencat: juny de 2022)
• .
• (Enllaç trencat: giner de 2020)
• .
• (2000).«Social network analysis: a handbook».Sage.

64–69..

• (1981).«Methods for visual understanding of hierarchical system structures».IEEE Transactions on Systems, Man, and Cybernetics.SMC-11(2)

109–125.doi:10.1109/TSMC.1981.4308636..

• .
• «What is a Dessin d'Enfant».Notices of the American Mathematical Society.50

788–789..