Pagguhit ng talangguhit

Mula sa Tagalog na Wikipedia, ang malayang ensiklopedya

Ang pagdrowing ng grap, bilang isang sangay ng teoriyang grap, ay inaaplay ang topolohiya at heometriya upang ma-derive ang dalawahan at tatluhang dimensiyon na paglalarawan ng grap. Ang pagdrowing ng grap ay ginayak ng mga aplikasyong tulad ng pagdisenyo ng circuit na VLSI, pag-analisa ng network na panglipunan, kartograpiya at bioinformatics.

[baguhin] Kabuuang tanaw

Kadalasang inilalarawan ang mga grap sa pamamagitan ng tuldok para sa vertex, at arc para sa edge na nagdurugtong sa vertex. Maaaring gumamit ng mga pana upang maipakita ang oryentasyon ng directed edge. Tandaan na ang paglalarawang ito ng grap (isang layout ng grap o pag-embed) ay hindi dapat ipagkamali sa grap mismo (isang abstrakto, di-grapikal na istruktura). Ang iba-ibang layout ay puwedeng iugnay sa iisang grap. Sa abstrakto, ang mahalaga lamang ay kung aling vertex ang karugtong ng iba pa sa pmamagitan ng ilang edge. Magkagayunman, sa konkreto ang pagsasaayos ng mga vertex at edge 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:

• force-based na layout: gradient-descent minimization ng function ng energy batay sa pisikal na metapora na may kinalaman sa molecular mechanics.
• spectral na layout: layout na ginagamit ang mga coordinate ng mga eigenvector ng isang matrix tulad ng Laplacian na na-derive sa adjacency matrix ng graph.
• orthogonal na layout: layout na ang mga edge ay nakahiga o nakatayo, na may dulog na pinaliliit ang bilang ng pagkukrus ng mga edge at area na saklaw. Mahalaga ito sa mga larangan ng disenyo ng layout ng VLSI at PCB.
• symmetric na layout: tinatangka nitong makakita ng pangkat ng symmetry sa grap.
• tree na layout: ipinapakita nito ang isang may ugat na parang puno na kaanyuan, na angkop para sa mga tree (i.e., grap na walang siklo).
• hierarchical na mga layout: tinatangka nitong makakita ng source at sink sa loob ng isang directed grap at iayos ang mga node nang pa-layer, na ang karamihan sa edge ay nagsisimula sa source at dumadaloy sa direksiyon ng sink.

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

[baguhin] Metrics

K₄ (the (ang kumpletong grap na may 4 na vertex) ay maidodrowing na mayroon o walang nag-ooverlap na edge (igalaw ang isang sulok sa loob ng tatsulok na nilikha ng tatlong iba pang sulok)

Walang "pinakamahusay" na layout - 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 edge. May ilang grap na hindi maidodrowing nang walang pagkrus ng mga edge, nguni't 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 edge hangga't maaari.

Ang isa pang posibleng sukatan ay ang lapit ng mga vertex, maraming grap ang mas magandang tingnan kung ang di-adjacent na vertex ay hindi ipo-plot nang magkadikit. Ang isa pang sukatan ay ang lapit ng vertex sa isang di-adjacent na edge, and distansiyang ito ay kailangang sapat ang laki para sa isang magandang itsura.

[baguhin] Uri ng pagdrowing ng grap

• Dayagram na Hasse, isang uri ng pagdrowing ng grap na natatangi para sa mga partial order
• Dessin d'enfant, isang uri ng pagdrowing ng grap na ginagamit sa aldyibraikong heometriya
• Dayagram na IState, paglalarawan ng mga finite state machine

[baguhin] Dagdag na babasahin

• Giuseppe Di Battista, Peter Eades, Roberto Tamassia and Ioannis G. Tollis (1991). Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall.
• Giuseppe Di Battista, Peter Eades, Roberto Tamassia and 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

[baguhin] Panlabas na kawing

• Graphdrawing.org: opisyal na web site ng Graph Drawing Steering Committee, organisador ng taunang International Symposium sa Graph Drawing. May deskripsiyon ng graphml graph description language, halimbawa ng datos ng graph, at kawing sa iba pang rekurso sa pagdrowing ng grap.
• Graph drawing e-print archive: may impormasyon sa mga papel mula sa lahat ng Graph Drawing symposia.
• Pagdrowing ng grap sa Open Directory Project para sa dagdag ng kawing na may kaugnayan sa pagdrowing ng grap.