DNS gráfok

A G = (V, X) párost, ahol V tetszőleges nem üres véges halmaz, X pedig a V különböző elemeiből képzett rendezetlen párokból álló halmaz, gráfnak nevezzük. A V elemeit a gráf csúcsainak, az X elemeit pedig a gráf éleinek nevezzük.

Az X-hez tartozó tetszőleges x = {u, v} rendezetlen pár az u és a v csúcsokat összekötő él. Az x = {u, v} él és az u, illetve v csúcsok illeszkednek. Ha két különböző x és y él ugyanahhoz a csúcshoz illeszkednek, akkor azt mondjuk, hogy az x és y élek szomszédosak. A p csúcsból és q élből álló gráfot (p, q) gráfnak nevezzük.

A G = (V, X) párost, ahol V tetszőleges nem üres véges halmaz, X pedig a V különböző elemeiből képzett rendezett párokból álló halmaz, orientált gráfnak nevezzük. Az X elemeit orientált éleknek nevezzük. Az orientált {x, y} és {y, x} éleket tetszőleges x és y esetén szimmetrikus élpárnak nevezzük. Azokat az orientált gráfokat, amelyek nem tartalmaznak szimmetrikus orientált élpárt irányított gráfoknak nevezzük.

Valamely G gráfban egy váltakozóan csúcsokból és élekből álló v_{0}, x_{1}, v_{1}, ...v_{n−1}, x_{n}, v_{n} sorozatot láncolatnak nevezzük, ha a sorozat csúccsal kezdődik és végződik, továbbá, ha minden a sorozatban előforduló él illeszkedik az őt közvetlen megelőző, illetve az őt közvetlen követő csúcshoz. Az n értéket a láncolat hosszának nevezzük. Valamely láncolat hossza tehát a benne előforduló élek számával egyezik meg. Azt mondjuk, hogy a v_{0}, x_{1}, v_{1}, ...v_{n−1}, x_{n}, v_{n} láncolat a v_{0} és a v_{n} csúcsokat köti össze. Az elmondottakból következik, hogy valamely v_{0}, x_{1}, v_{1}, ...v_{n−1}, x_{n}, v_{n} láncolatot egyértelműen meghatároz a benne előforduló v_{0}, v_{1}, ...v_{n−1}, v_{n} csúcsok sorozata. A v_{0} csúcsot a lácolat kezdő, a v_{n} csúcsot pedig a láncolat végcsúcsának nevezzük. A láncolat zárt, ha v_{0} = v_{n}, különben nyílt.

Valamely láncolatot láncnak nevezzük, ha benne minden él különböző. Valamely láncolatot egyszerű láncnak, vagy útnak nevezzük, ha benne minden csúcs különböző. Könnyen látható, hogy minden egyszerű lánc egyúttal lánc is.

A zárt láncot ciklusnak nevezzük. Valamely v_{0}, x_{1}, v_{1}, ...v_{n−1}, x_{n}, v_{n} zárt láncolatot egyszerű ciklusnak, vagy körnek nevezünk, ha a v_{1}, ..., v_{n} csúcsok mind különbözőek és n ≥ 3.

A G gráf összefüggő, ha bármely két csúcsa összeköthető egyszerű lánccal (úttal). Valamely G gráf aciklikus, ha nicsen benne ciklus. Az összefüggő és aciklikus gráfot

fának nevezzük.

Legyen a G = (V, X) gráf fa. Legyen továbbá v_{0} a V csúcsok halmazának egy kitüntetett eleme, amelyet a továbbiakban a G fa gyökér pontjának nevezzük. Mivel a feltevés szerint a G gráf fa, ezért bármely v_{0}-tól különböző v csúcshoz létezik pontosan

Typeset by AMS-TEX

egy olyan út a gráfban, amely a v_{0} csúcsot a v csúccsal köti össze. Mint láttuk, egy ilyen út az őt képező csúcsok sorozatával adható meg.

Tegyük fel, hogy adott egy C címkehalmaz, amely számossága elegendően nagy ahhoz, hogy ha igény merül fel arra, hogy a csúcsok valamely V′ részhalmazát a C-be képezzük kölcsönösen egyértelműen, azaz megkülönböztető címkéket rendeljünk a V′ elelmeihez, akkor ez mindíg elvégezhető. A gyakorlatban a C általában valamely ABC feletti korlátos hosszúságú szavakból álló halmaz.

Lokális címkézés:. Rendeljünk egy tetszés szerinti címkét a v_{0} csúcshoz. Rendeljünk különböző címkéket mindazon v csúcsokhoz, amelyekre {v_{0}, v} ∈ V. Könnyen látható, pontsan ezek a csúcsok azok, amelyek a v_{0}-ból 1 hosszúságú úttal elérhetőek. Általában, ha a v_{0}-tól n hosszúságú úttal összeköthető csúcsokhoz már rendeltünk címkéket, akkor a v_{0}-tól n + 1 hosszúságú úttal összeköthető csúcsokhoz, ha egyáltalán ilyen létezik, úgy rendeljünk címkéket, hogy két ilyen v_{1} és v_{2} csúcs szükségképpen különböző cimkét kapjon, ha létezik olyan \overline{v}, amely a v_{0}-ból n hosszúságú úttal elérhető, és \{\overline{v}, v_{1}\} ∈ X, illetve \{\overline{v}, v_{2}\} ∈ X.

Tétel:. Legyen (G, v_{0}) v_{0} gyökerű fa. Rendeljünk a lokális címkézési algoritmus szerint címkéket a G gráf csúcsaihoz. Reprezentáljuk a v_{0} csúcsot a címkéjével (egy elemből álló címkesorozat). Általában minden v_{0}-tól különböző v csúcsot, reprezentáljunk azzal a cimkesorozattal, amelyet úgy kapunk, hogy tekintjük a v_{0}-ból a v-be vezető egyetlen v_{0}, ..., v_{n} = v utat és a benne előforduló csúcsokat a hozzájuk rendelt címkékkel helyettesítjük.

A különböző csúcsokhoz ilyen módon hozzárendelt címkesorozatok külőnbözőek.

Bizonyítás. A bizonyítás teljes indukcióval történik. Legyen c egy olyan címkesorozat, amely egyetlen címkéből áll, és amelyhez van olyan csúcs, amelyhez rendelt címkesorozat pontosan a c. A címkézési algoritmus szerint olyan csúcs, amelyhez rendelt címkesorozat egyetlen címkéből áll, pontosan egy van, és ez a v_{0} gyökérpont. Tegyük fel, hogy valamely n ≥ 1-re igaz, hogy ha a c címkesorozat n elemű, akkor legfeljebb egy olyan csúcspont van V -ben, amelyhez rendelt címke a c. Legyen c n + 1 hosszúságá címkesorozat és tegyük fel, hogy van olyan csúcs, amelyekhez rendelt címkesorozat a c. Legyenek v′ és v′′ ilyen csúcsok. Tekintsük a v_{0}-ból a v′, valamint a v_{0}-ból a v′′ csúcsokba vezető v_{0}, v′_{1}, ..., v′_{n+1} = v′, illetve a v_{0}, v′′_{1}, ..., v′′_{n+1} = v′′ utakat. Vegyük észre, hogy a v′_{n} és a v′′_{n} csúcsokhoz ugyanaz az n hosszúságá címkesorozat tartozik. Ezért a feltevés szerint a v′_{n} és a v′′_{n} csúcsok azonosak. A címkézési algoritmus szerint, mivel a c címkesorozat utolsó eleme egyaránt a v′ és a v′′ csúcsokhoz is van rendelve, ezért a két csúcs azonos.

A fentiekből következik, hogy bármely két külöböző csúcshoz rendelt címkesorozat szükségképpen különböző.