Directed vs Undirected Graph
Ib daim duab yog cov qauv lej uas yog tsim los ntawm cov kab ntsug thiab cov npoo. Ib daim duab sawv cev rau ib pawg ntawm cov khoom (sawv cev los ntawm vertices) uas txuas nrog qee qhov txuas (sawv cev los ntawm ntug). Siv cov lej cim, ib daim duab tuaj yeem sawv cev los ntawm G, qhov twg G=(V, E) thiab V yog txheej ntawm vertices thiab E yog cov npoo. Nyob rau hauv ib daim duab tsis muaj kev taw qhia tsis muaj kev taw qhia cuam tshuam nrog cov npoo uas txuas cov vertices. Hauv daim duab qhia muaj ib qho kev taw qhia cuam tshuam nrog cov npoo uas txuas cov vertices.
Undirected Graph
Raws li tau hais ua ntej, daim duab tsis qhia yog ib daim duab uas tsis muaj kev taw qhia ntawm cov npoo uas txuas cov vertices hauv daim duab. Daim duab 1 depicts ib daim duab undirected nrog set ntawm vertices V={V1, V2, V3}. Cov npoo ntawm cov duab saum toj no tuaj yeem sau ua V={(V1, V2), (V2, V3), (V1, V3)}. Nws tuaj yeem raug sau tseg tias tsis muaj dab tsi tiv thaiv kev sau cov npoo li V={(V2, V1), (V3, V2), (V3, V1)} vim cov npoo tsis muaj kev taw qhia. Yog li cov npoo hauv ib daim duab uas tsis muaj kev taw qhia tsis tau txiav txim ua khub. Qhov no yog lub ntsiab yam ntxwv ntawm ib tug undirected graph. Undirected graphs tuaj yeem siv los sawv cev kev sib raug zoo ntawm cov khoom uas sawv cev los ntawm vertices. Piv txwv li, ob txoj kev sib txuas ntawm txoj kev sib txuas ntawm cov nroog tuaj yeem sawv cev siv cov duab tsis qhia. Cov nroog tuaj yeem sawv cev los ntawm cov vertices hauv daim duab thiab cov npoo sawv cev rau ob txoj kev uas txuas cov nroog.
Directed Graph
Ib daim duab qhia yog ib daim duab uas cov npoo hauv daim duab uas txuas cov vertices muaj kev taw qhia. Daim duab 2 qhia txog daim duab qhia nrog teeb tsa V={V1, V2, V3}. Cov npoo ntawm cov duab saum toj no tuaj yeem sau ua V={(V1, V2), (V2, V3), (V1, V3)}. Ntug nyob rau hauv ib daim duab undirected yog txiav txim khub. Raws li txoj cai, ntug e hauv daim duab qhia tuaj yeem sawv cev los ntawm kev txiav txim khub e=(x, y) qhov twg x yog lub vertex uas yog hu ua lub hauv paus, qhov chaw lossis qhov chaw pib ntawm ntug e, thiab vertex y yog hu ua terminus, terminating vertex lossis terminal point. Piv txwv li, txoj kev sib txuas ntawm cov nroog uas siv ib txoj hauv kev tuaj yeem sawv cev siv cov duab tsis qhia. Cov nroog tuaj yeem sawv cev los ntawm cov vertices hauv daim duab thiab cov npoo qhia sawv cev rau txoj kev uas txuas cov nroog xav txog cov kev taw qhia uas cov tsheb khiav hauv txoj kev.
Dab tsi yog qhov txawv ntawm Directed Graph thiab Undirected Graph?
Nyob rau hauv daim duab qhia ib ntug yog ib khub txiav txim, qhov twg tus khub txiav txim sawv cev rau cov kev taw qhia ntawm ntug uas txuas ob vertices. Ntawm qhov tod tes, nyob rau hauv ib qho kev qhia tsis ncaj ncees, ib qho ntug yog ib khub tsis muaj kev txiav txim, vim tsis muaj kev taw qhia cuam tshuam nrog ntug. Cov duab uas tsis muaj kev taw qhia tuaj yeem siv los sawv cev kev sib raug zoo ntawm cov khoom. Nyob rau hauv-degree thiab tawm-degree ntawm txhua qhov ntawm ib qho kev qhia tsis ncaj ncees yog sib npaug tab sis qhov no tsis muaj tseeb rau daim duab qhia. Thaum siv lub matrix los sawv cev rau cov duab tsis qhia, lub matrix ib txwm dhau los ua cov duab sib luag, tab sis qhov no tsis muaj tseeb rau cov duab qhia. Ib daim duab uas tsis muaj kev taw qhia tuaj yeem hloov mus rau cov duab qhia los ntawm kev hloov txhua tus ntug nrog ob txoj kab ncaj nraim mus rau qhov sib txawv. Txawm li cas los xij, nws tsis tuaj yeem hloov daim duab qhia mus rau ib qho kev qhia tsis ncaj ncees.
