Pagguhit ng grap

Ang pagdrowing ng grap o pagguhit ng talangguhit, bilang isang sangay ng teoriyang grap, ay inaaplay ang topolohiya at heometriya upang mahango ang dalawahan at tatluhang dimensiyon na paglalarawan ng grap. Ang pagdrowing ng grap ay ginayak ng mga aplikasyong tulad ng pagdisenyo ng sirkitong VLSI, pag-analisa ng network na panglipunan, kartograpiya, at biyoimpormatika.

Kabuuang tanaw

Kadalasang inilalarawan ang mga grap sa pamamagitan ng tuldok para sa berteks, at arko para sa gilid na nagdurugtong sa berteks. Maaaring gumamit ng mga pana upang maipakita ang oryentasyon ng itinuturong gilid. Tandaan na ang paglalarawang ito ng grap (isang balangkas ng grap o pagbabaon) ay hindi dapat ipagkamali sa grap mismo (isang abstrakto, di-grapikal na istruktura). Ang iba-ibang balangkas ay puwedeng iugnay sa iisang grap. Sa abstrakto, ang mahalaga lamang ay kung aling vertex ang karugtong ng iba pa sa pamamagitan ng ilang gilid. Magkagayunman, sa konkreto ang pagsasaayos ng mga berteks at gilid na ito ay nakaaapekto sa pagkaunawa, kapakinabangan, gastos sa paglikha, at kagandahan ng larawan ng grap.

Batay sa mga konsepto at paala-alang ito, may iba-ibang istratehiya ng paglayout ng grap, tulad ng:

balangkas na batay sa puwersa: may gradong pagbaba ng minimisasyon o pagpapahina ng tungkulin ng enerhiya batay sa pisikal na metapora na may kinalaman sa molekular na mekaniks.
ispektral na balangkas: balangkas na ginagamit ang mga koordinado ng eigenbektor ng isang matriks tulad ng Laplasyano na nahango sa pagiging matriks ng pagiging magkatabi ng grap.
ortogonal na balangkas: balangkas na ang mga gilid ay nakahiga o nakatayo, na may dulog na pinaliliit ang bilang ng pagkukrus ng mga gilid at areang saklaw. Mahalaga ito sa mga larangan ng disenyo ng layout ng VLSI at PCB.
simetrikong balangkas: tinatangka nitong makakita ng pangkat ng simetriya sa grap.
balangkas na puno: ipinapakita nito ang isang may ugat na parang puno na kaanyuan, na angkop para sa mga puno (iyong grap na walang siklo).
hirarkikal na mga balangkas: tinatangka nitong makakita ng pinagkunan at lundo o paglubog sa loob ng isang direktadong grap at iayos ang mga noda nang pasapin-sapin, na ang karamihan sa gilid ay nagsisimula sa pinagkunane at dumadaloy sa direksiyon ng lundo.

Sa maraming aplikasyon ng pagdrowing ng grap importanteng tukuyin, ipatupad, at beripikahin nang pormal ang mga ganitong proseso.

Metriko

K₄ (ang kumpletong grap na may 4 na berteks) ay maidodrowing na mayroon o walang nagpapatung-patong na gilid (igalaw ang isang sulok sa loob ng tatsulok na nilikha ng tatlong iba pang sulok)

Walang "pinakamahusay" na balangkas - ang iba't-ibang paraan ng pagdispley ng grap ay nagbibigay diin sa iba't-ibang katangian. Ang isang sukat ng kalidad ng isang algoritmo ng pagdrowing ng grap ay ang bilang ng maidodrowing nitong pagkrus ng gilid. May ilang grap na hindi maidodrowing nang walang pagkrus ng mga gilid, ngunit ang ilan naman ay maidodrowing nang wala nito. Ang tawag sa huli ay mga planar grap. Ayon sa metric na ito, ang "mahusay" na algoritmo ay nagdodrowing ng grap na may pinakakaunting pagkukrus ng gilid hangga't maaari.

Ang isa pang posibleng sukatan ay ang lapit ng mga vertex, maraming grap ang mas magandang tingnan kung ang di-katabing berteks ay hindi imamarka o iguguhit nang magkadikit. Ang isa pang sukatan ay ang lapit ng berteks sa isang di-katabing gilid, and distansiyang ito ay kailangang sapat ang laki para sa isang magandang itsura.

Uri ng pagdrowing ng grap

Dayagram na Hasse, isang uri ng pagdrowing ng grap na natatangi para sa mga ordeng hindi buo
Dessin d'enfant, isang uri ng pagdrowing ng grap na ginagamit sa alhibraiko o maka-alhebrang heometriya
Dayagram na IState, paglalarawan ng mga makinang may kalagayang may-hangganan

Dagdag na babasahin

Giuseppe Di Battista, Peter Eades, Roberto Tamassia at Ioannis G. Tollis (1991). graph Drawing: Algorithms for the Visualization of graphs. Prentice Hall.
Giuseppe Di Battista, Peter Eades, Roberto Tamassia at Ioannis G. Tollis (1994). "Algorithms for Drawing graphs: an Annotated Bibliography". Sa: Computational Geometry: Theory and Applications 4:235-282. (http://www.cs.brown.edu/people/rt/gd.html)
Isabel F. Cruz, Roberto Tamassia. graph Drawing Tutorial. (http://www.cs.brown.edu/people/rt/gd.html)

Panlabas na kawing

graphdrawing.org: opisyal na websayt ng graph Drawing Steering Committee, organisador ng taunang International Symposium sa pagguhit ng talangguhit. May deskripsiyon ng wika ng paglalarawan ng grap, halimbawa ng datos ng grap, at kawing sa iba pang rekurso sa pagdrowing ng grap.
Arkibo ng elektronikong paglilimbag ng drowing ng grap: may impormasyon sa mga papel mula sa lahat ng simposiya ng pagguhit ng talangguhit.
Pagdrowing ng grap sa Proyekto ng Bukas na Direktoryo para sa dagdag na kawing na may kaugnayan sa pagdrowing ng grap.