Ero suunnatun ja suuntaamattoman kuvaajan välillä

Ohjattu vs. suunnaton kuvaaja

Kaavio on matemaattinen rakenne, joka koostuu joukosta huippuja ja reunoja. Kaavio edustaa joukko objekteja (joita edustavat tiput), jotka on kytketty joidenkin linkkien kautta (reunat). Matemaattisia merkintöjä käyttämällä kuvaaja voidaan esittää G: llä, jossa G = (V, E) ja V on kärkipiste ja E on reunajoukko. Suuntaamattomassa kuvaajassa kärkien yhdistäviin reunoihin ei ole suunnattua suuntaa. Osoitetussa kuvaajassa on suunta, joka liittyy reunoihin, jotka yhdistävät kärjet.

Suuntaamaton kuvaaja

Kuten aikaisemmin mainittiin, suuntaamaton kuvaaja on kuvaaja, jossa reunoissa ei ole suuntaa, jotka yhdistävät kuvaajan kärjet. Kuvio 1 kuvaa suuntaamatonta kuvaajaa, jossa on joukko huipuja V = V1, V2, V3. Yllä olevan kaavion reunajoukot voidaan kirjoittaa muodolla V = (V1, V2), (V2, V3), (V1, V3). Voidaan myös huomata, että mikään ei estä reunajoukon kirjoittamista nimellä V = (V2, V1), (V3, V2), (V3, V1), koska reunoilla ei ole suuntaa. Siksi suuntaamattoman kuvaajan reunoja ei järjestetä pareiksi. Tämä on suunnatun kuvaajan pääominaisuus. Suuntaamattomia kuvaajia voidaan käyttää symmetristen suhteiden esittämiseen objektien välillä, joita edustavat tiput. Esimerkiksi kaksisuuntainen tieverkko, joka yhdistää joukon kaupunkeja, voidaan esittää ohjaamattoman kaavion avulla. Kaupungit voidaan edustaa kuvaajan kärkipisteillä ja reunat edustavat kaupunkien yhdistäviä kaksisuuntaisia ​​teitä.

Ohjattu kuvaaja

Suunnattu kuvaaja on kuvaaja, jossa kärkiä yhdistävien kuvaajan reunoilla on suunta. Kuvio 2 kuvaa suunnattua kuvaajaa, jossa on joukko huipuja V = V1, V2, V3. Yllä olevan kaavion reunajoukot voidaan kirjoittaa muodolla V = (V1, V2), (V2, V3), (V1, V3). Ohjaamattoman kuvaajan reunat on järjestetty pareittain. Muodollisesti reuna e voidaan suunnatussa kuvaajassa esittää tilatulla parilla e = (x, y), missä x on kärkipiste, jota kutsutaan reunan e alkuperäiseksi, lähteeksi tai lähtöpisteeksi, ja kärkipistettä y kutsutaan päätteeksi , päätepiste tai päätepiste. Esimerkiksi tieverkko, joka yhdistää joukon kaupunkeja yksisuuntaisilla teillä, voidaan edustaa ohjaamattoman kaavion avulla. Kaupungit voidaan edustaa kuvaajan kärkipisteillä ja suunnatut reunat edustavat kaupunkeja yhdistäviä teitä ottaen huomioon liikenteen suunta tiellä.

Mitä eroa on suunnatun kuvaajan ja suunnatun kuvaajan välillä??

Suunnatussa kuvaajassa reuna on järjestetty pari, jossa tilattu pari edustaa reunan suuntaa, joka yhdistää kaksi kärkeä. Toisaalta suuntaamattomassa kuvaajassa reuna on järjestämätön pari, koska reunaan ei ole liitetty suuntaa. Ohjaamattomia kuvaajia voidaan käyttää esittämään symmetrisiä suhteita objektien välillä. Kunkin solmun aste- ja ulkoasteet ohjaamattomassa kuvaajassa ovat yhtä suuret, mutta tämä ei pidä paikkaansa osoitetussa kuvaajassa. Kun matriisia käytetään suuntaamattoman kaavion esittämiseen, matriisista tulee aina symmetrinen kuvaaja, mutta tämä ei pidä paikkaansa suunnattuja kuvaajia. Suuntaamaton kuvaaja voidaan muuntaa suunnattuksi kuvaajaksi korvaamalla jokainen reuna kahdella suunnatulla reunalla, jotka menevät vastakkaiseen suuntaan. Suunnattua kuvaajaa ei kuitenkaan ole mahdollista muuntaa ohjaamattomaksi kuvaajaksi.