Vertex (graafiteoria)

Graafiteoriassa kärki on perusyksikkö, joka muodostaa graafit - suuntaamaton graafi koostuu monista pisteistä ja monista reunoista (järjestämättömät kärkiparit), kun taas suunnattu graafi koostuu monista pisteistä ja monista kaarista (järjestetyt pisteparit). Graafia esittävissä piirustuksissa kärki on yleensä merkitty ympyrällä, jossa on etiketti, reuna viivalla ja kaari nuolella, joka yhdistää kärjet.

Graafiteorian näkökulmasta kärkipisteitä käsitellään piirteettöminä jakamattomina objekteina, vaikka ne voivat edustaa jotain rakennetta riippuen ongelmasta, josta graafi on peräisin. Esimerkiksi semanttinen verkko  on graafi, jossa kärjet edustavat objektien luokan käsitettä.

Kahta kärkeä, jotka muodostavat reunan, kutsutaan reunan päätypisteiksi, ja reunan sanotaan olevan kärkipisteisiin kohdistuva. Huippupisteen w sanotaan olevan toisen kärjen v vieressä, jos graafi sisältää reunan ( v , w ). Huippupisteen v lähialue on generoitu aligraafi , jonka muodostavat kaikki v :n vieressä olevat kärjet .

Vertex-tyypit

Graafin kärjen aste on sille osuvien reunojen lukumäärä. Vertexiä kutsutaan eristetyksi , jos sen aste on nolla. Eli se on kärki, joka ei ole minkään reunan loppu. Huippupistettä kutsutaan lehdeksi (tai riippuvaksi ), jos sen aste on yksi. Suunnattu graafi erottaa ulkoasteen (lähtevien kaarien määrä) ja sisäänasteen (saapuvien reunojen lukumäärä). Lähdettä kutsutaan kärjeksi, jonka sisään-aste on nolla, ja kärkeä, jonka ulko-aste on nolla, kutsutaan nieluksi .

Sarana on kärki, jonka poistaminen johtaa graafin yhdistettyjen komponenttien lisääntymiseen. Vertex-erotin on joukko pisteitä, joiden poistaminen johtaa graafin yhdistettyjen komponenttien kasvuun. Huipulla k-kytketty graafi  on sellainen, jossa alle k pisteen poistaminen jättää graafin aina yhteen. Itsenäinen joukko on joukko pisteitä, joista ei ole kahta vierekkäistä, ja kärjen kansi on joukko pisteitä, jotka sisältävät vähintään yhden graafin minkä tahansa reunan päätypisteen. Graafin kärkien vektoriavaruus on vektoriavaruus, jonka perustana ovat graafin kärkipisteitä vastaavat vektorit (lukukentän {0, 1} yli) [1] [2] .

Graafin sanotaan olevan kärkitransitiivinen, jos siinä on symmetrioita, jotka vievät minkä tahansa kärjen mihin tahansa toiseen kärkeen. Graafeiden numeroinnin ja graafin isomorfismin yhteydessä on tärkeää erottaa nimetyt ja merkitsemättömät pisteet . Merkitty kärkipiste on kärkeen liittyvä lisätieto, joka erottaa sen muista merkityistä pisteistä. Kahta kuvaajaa voidaan pitää isomorfisena vain, jos isomorfismi vie pisteet pisteisiin, joilla on samat tunnisteet. Merkitsemättömät kärjet voidaan sitten kääntää toisiksi pisteiksi vain vierekkäisyyden perusteella ja ilman lisätietoa.

Graafin kärjet ovat samanlaisia ​​kuin polytoopin kärjet , mutta ne eivät ole samoja - polytoopin luuranko muodostaa graafin, jonka kärjet ovat polytoopin kärjet, mutta polytoopin kärjeissä on ylimääräinen rakenne (geometrinen sijainti), joka jätetään huomioimatta graafiteoriassa. Monitahoisen kärkikuvio on samanlainen kuin graafin kärjen ympäristö.

Katso myös

Muistiinpanot

  1. ↑ M. Swami, K. Tulasimaran. Graafit, verkot ja algoritmit. - Moskova: Mir, 1984. - S. 62-76. luku 4
  2. ↑ Reinhard Distel. Graafiteoria. - Novosibirsk: Matematiikan instituutin kustantamo, 2002. - s. 35.

Linkit

  Siirry Wikidata-kohteeseen  Sanakirjat ja tietosanakirjat