Pagguhit ng grapo

Mula sa Wikipediang Tagalog, ang malayang ensiklopedya
Tumalon sa: nabigasyon, hanapin

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

Kabuuang tanaw[baguhin]

Kadalasang inilalarawan ang mga grapo 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 grapo (isang balangkas ng grapo o pagbabaon) ay hindi dapat ipagkamali sa grapo mismo (isang abstrakto, di-grapikal na istruktura). Ang iba-ibang balangkas ay puwedeng iugnay sa iisang grapo. 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 grapo.

Batay sa mga konsepto at paala-alang ito, may iba-ibang istratehiya ng paglayout ng grapo, 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 koordinato ng eigenbektor ng isang matriks tulad ng Laplasyano na nahango sa pagiging matriks ng pagiging magkatabi ng grapo.
  • 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 grapo.
  • balangkas na puno: ipinapakita nito ang isang may ugat na parang puno na kaanyuan, na angkop para sa mga puno (iyong grapo na walang siklo).
  • hirarkikal na mga balangkas: tinatangka nitong makakita ng pinagkunan at lundo o paglubog sa loob ng isang direktadong grapo 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 grapo importanteng tukuyin, ipatupad, at beripikahin nang pormal ang mga ganitong proseso.

Metriko[baguhin]

K4 (ang kumpletong grapo 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 grapo ay nagbibigay diin sa iba't-ibang katangian. Ang isang sukat ng kalidad ng isang algoritmo ng pagdrowing ng grapo ay ang bilang ng maidodrowing nitong pagkrus ng gilid. May ilang grapo 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 grapo. Ayon sa metric na ito, ang "mahusay" na algoritmo ay nagdodrowing ng grapo na may pinakakaunting pagkukrus ng gilid hangga't maaari.

Ang isa pang posibleng sukatan ay ang lapit ng mga vertex, maraming grapo 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 grapo[baguhin]

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

Dagdag na babasahin[baguhin]

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

Panlabas na kawing[baguhin]

  • 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 grapo, halimbawa ng datos ng grapo, at kawing sa iba pang rekurso sa pagdrowing ng grapo.
  • Arkibo ng elektronikong paglilimbag ng drowing ng grapo: may impormasyon sa mga papel mula sa lahat ng simposiya ng pagguhit ng talangguhit.
  • Pagdrowing ng grapo sa Proyekto ng Bukas na Direktoryo para sa dagdag na kawing na may kaugnayan sa pagdrowing ng grapo.