Ang grap ay binubuo ng mga vertex at gilid. Ang mga vertex ay konektado sa pamamagitan ng mga gilid ayon sa isang tiyak na pag-aari - ang ugnayan ng insidente, na tumutukoy sa hanay ng mga gilid. Sa kasong ito, maaaring mabuo ang mga loop at mga nakahiwalay na verte.
Panuto
Hakbang 1
Hayaang maibigay ang hanay ng mga gilid ng grapiko at ibigay ang ugnayan na posible na gumuhit ng isang gilid mula sa isang tuktok patungo sa isa pa. Bilang isang halimbawa, ang hanay ng mga vertex na {1, 2, 3, 4, 5, 6, 7, 8}, dalawang mga vertex x at y ay nasa ratio x + y <8.
Hakbang 2
Bumuo ng isang vertex adjacency matrix. Upang gawin ito, bumuo ng isang parisukat na talahanayan, ang bilang ng mga hilera at haligi sa talahanayan ay kasabay ng bilang ng mga vertex. Pagkatapos ay ilagay ang 1 sa intersection ng i-th row at j-th na haligi kung ang mga vertex na i at j ay nasiyahan ang ibinigay na ratio. Ilagay ang 0 sa intersection ng i-th row at j-th na haligi kung hindi natutugunan ang ratio para sa mga kaukulang elemento.
Sa aming halimbawa, ang unang linya ay napunan tulad ng sumusunod:
1 + 1 <8, kaya may 1 sa intersection ng 1st row at 1st haligi
1 + 2 <8, muli 1
1 + 3 <8, muli 1
1 + 7 <8, maling hindi pagkakapantay-pantay, kaya ang elementong ito ng talahanayan ay magiging 0
1 + 8 <8, muli 0
Hakbang 3
Upang malaman ang bilang ng mga gilid, bilangin ang bilang ng mga nasa adjacency matrix nang hindi doblehin ang mga gilid.
Sa halimbawa, isang simetriko matrix ang nakuha, kaya binibilang muna namin ang mga nasa itaas ng pangunahing dayagonal ng matrix (minarkahan ng asul), at pagkatapos ang mga nasa pangunahing dayagonal (minarkahan ng pula). Ang kabuuang bilang ng mga tadyang ay 12.
Hakbang 4
Bumuo ng isang matrix ng mga insidente (gilid). Upang gawin ito, gumuhit ng isang talahanayan, ang bilang ng mga hilera dito ay katumbas ng bilang ng mga vertex sa grap, at ang bilang ng mga haligi ay katumbas ng bilang ng mga gilid. Ilagay ang mga yunit sa mga linyang iyon na konektado sa isang gilid. Ang mga gilid na humahantong mula sa tuktok papunta dito ay tinatawag na mga loop at idinagdag sa dulo ng matrix. Sa mga haligi na naaayon sa mga loop, mayroon lamang isang yunit, sa kaibahan sa natitirang mga gilid.
Hakbang 5
Ngayon ay gumuhit ng isang graph. Ilagay ang mga vertex sa papel sa anumang paraan at ikonekta ang mga ito sa mga gilid gamit ang mga itinakdang talahanayan. Ang mga Vertice na hindi konektado sa pamamagitan ng mga gilid ay tinatawag na nakahiwalay.
