Glosaro de grafeteorio

background image

Glosaro de grafeteorio

1

Glosaro de grafeteorio

Grafeteorio estas kreska areo en matematika esplorado, kaj havas grandan fakan vortoprovizon. Kelkaj aŭtoroj uzas

la saman vorton kun malsamaj signifoj. Aliaj aŭtoroj uzas malsamajn vortojn celante la saman aferon. Ĉi tiu paĝo

provizas la superrigardon pri nuntempa terminaro de grafeteorio kaj provas teni sin laŭeble ĝisdatigita kun la aktuala

lingvouzo.

Fundamentaĵoj

Grafeo G konsistas el du tipoj de eroj, nome verticoj kaj randoj. Ĉiu rando havas du finpunktojn en la aro de

verticoj, kaj oni povas diri, ke randoj interkonektas kunligas tiujn du finpunktojn. La aro de randoj tial povas

esti difinita kiel sub-aro de la familio de ĉiuj du-eraj aroj de verticoj. Ofte, tamen, la aro de verticoj estas konsiderata

kiel aro, kaj estas incida rilato kiu atribuas ĉiun randon al la paro de verticoj kiuj estas ĝiaj finpunktoj.

Randoj povas esti dotitaj kun direkto, kondukante al la nocio de orientita grafeo aŭ duliteraĵo, vidu sekcion

#Direkto.

Alternativaj modeloj de grafeo ekzistas; ekz., grafeo povas esti konsiderata kiel Bulea duuma funkcio super la aro de

verticoj aŭ kiel kvadrata (0,1)-matrico.

Vertico (baza ero) estas simple desegnita kiel punkto. La vertica aro de G estas kutime signita de V(G), aŭ V kiam

estas neniu danĝero de konfuzo. La ordo de grafeo estas la nombro de ĝiaj verticoj, kio estas |V(G)|.

Latero (aro de du eroj) estas desegnita kiel linio konektanta du verticojn, nomitajn finverticoj, aŭ finpunktoj. Rando

kun finverticoj x kaj y estas signata per xy (sen ia ajn simbolo en intere, do, ne skribu xy). La rando-aro de G estas

kutime signata per E(G), aŭ E kiam estas neniu danĝero de konfuzo.

La grandeco de grafeo estas la kvanto de ties lateroj, kio estas |E(G)|.

Ciklo estas latero kies finverticoj estas la sama vertico. Ligo havas du klarajn finverticojn. Latero estas multobla se

estas alia latero kun la samaj finverticoj; alie ĝi estas simpla. La obleco de latero estas la nombro de multaj randoj

kunhavantaj la samajn finverticojn; la obleco de grafeo estas la maksimuma obleco de ĝiaj lateroj. Grafeo estas

simpla grafeo se ĝi havas neniun multoblan lateron nek multoblan ciklon, plurgrafeo se ĝi havas multoblajn

laterojn, sed ne ciklojn, kaj plurgrafeo pseŭdografeo se ĝi enhavas kaj multoblajn laterojn kaj ciklojn (la

literaturo estas alte nekonsekvenca). Kiam dirite sen ia kondiĉo, grafeo estas preskaŭ ĉiam alprenita esti simpla — aŭ

oni devas juĝi laŭ la ĉirkaŭteksto.

Markado de grafeo kutime signifas la asignon de unikaj markoj (kutime naturaj nombroj) al la randoj kaj verticoj

de grafeo. Grafeoj kun markitaj (etikeditaj) lateroj aŭ verticoj estas nomataj kiel markitaj (etikeditaj), tiuj sen ĉi tio

estas nemarkitaj. Pli aparte, grafeoj kun markitaj verticoj nur estas vertico-markitaj, tiuj kun markitaj lateroj nur

estas latero-markitaj. (Ĉi tiu uzado estas por distingi inter grafeoj kun identigeblaj verticoj aŭ lateraj aroj

unuflanke, kaj izomorfiaj tipoj aŭ klasoj de grafeoj aliflanke.)

La ekzemplo grafeo bildita dekstre estas simpla grafeo kun vertica aro

V = {1, 2, 3, 4, 5, 6} kaj randa aro E = (kun la mapo w estante la

idento).

Hiperlatero estas rando kiu estas permesita alpreni iun ajn nombron de

verticoj, eble pli ol 2. Grafeo, kiu permesas iun ajn hiperlateron estas

nomita hipergrafeo. Simpla grafeo povas esti konsiderata speciala

kazo de la hipergrafeo, nome la 2-uniformo hipergrafeo. Tamen, kiam

komencita sen ia kondiĉo, latero estas ĉiam alprenita konsisti el

maksimume 2 verticoj, kaj grafeo estas neniam konfuzita kun

hipergrafeo.

background image

Glosaro de grafeteorio

2

Kontraŭ-latero estas latero, kiu "estas ne tie". Pli formale, por du verticoj u kaj v, {u, v} estas kontraŭ-latero en

grafeo G se (u, v) ne estas latero en G. Ĉi tio signifas, ke ne estas latero inter la du verticoj aŭ estas nur latero (v, u)

de v al u se G estas direktita.

Kontraŭ-triangulo estas aro de tri verticoj neniu el kiuj estas koneksa.

La komplemento

de grafeo G estas grafeo kun la sama vertica aro kiel G sed kun randa aro tia, ke xy estas rando

en

se kaj nur se xy estas ne rando en G.

Senlatera (latero-manka) grafeo malplena grafeo estas grafeo eble kun iuj verticoj, sed sen lateroj. Aŭ, ĝi estas

grafeo sen verticoj kaj sen lateroj.

La nula grafeo estas la grafeo sen verticoj kaj sen lateroj. Aŭ, ĝi estas grafeo sen lateroj kaj ia nombro de

verticoj, en kiu kazo ĝi povas nomiĝi la nula grafeo sur verticoj. (Estas nenia ajn konsekvenceco en la

literaturo.)

Grafeo estas malfinia se ĝi havas malfinie multajn verticojn aŭ randojn aŭ ambaŭ; alie la grafeo estas finia. Malfinia

grafeo kie ĉiu vertico havas finian gradon estas nomita loke finia. Kiam komencita sen ia kondiĉo, grafeo estas

kutime alprenita esti finia.

Du grafeoj G kaj H estas dirita esti izomorfiaj, signita per G ~ H, se estas (bijekcia, dissurĵeta) (unu-al-unu) rilato,

nomita izomorfio, inter la verticoj de la grafeo tia, ke du verticoj estas najbaraj en G se kaj nur se iliaj respektivaj

verticoj estas najbaraj en H. Simile, grafeo G estas dirita esti homomorfia al grafeo H se estas surĵeto (mapado),

nomita homomorfio, de V(G) al V(H) tia, ke se du verticoj estas interapudaj en G tiam iliaj respektivaj verticoj estas

interapudaj en H.

Subgrafeoj

Subgrafeo de grafeo G estas grafeo kies vertica kaj randa aroj estas subaroj de tiuj de G. En la mala direkto,

supergrafeo de grafeo G estas grafeo, kiu enhavas G kiel subgrafeo. Ni diras, ke grafeo G enhavas alian grafeon H

se iu subgrafeo de G estas H aŭ estas izomorfia al H (depende de la bezonoj de la situacio).

Subgrafeo H estas ampleksanta subgrafeo, aŭ faktoro, de grafeo G se ĝi havas la saman vertican aron kiel G. Ni

diras ke H ampleksas G.

Subgrafeo H de grafeo G estas dirita esti generita se, por iu ajn paro da verticoj x kaj y de H, xy estas rando de H se

kaj nur se xy estas rando de G. En alia vortoj, H estas generita subgrafeo de G se ĝi havas la plej randoj kiuj aperas

en G super la sama vertica aro. Se H estas elektita bazita sur vertica subaro S de V(G), tiam H povas esti skribita kiel

G[S] kaj estas dirita esti generita de S.

Grafeo kiu ne enhavas H kiel generita subgrafeo estas dirita esti H-libera.

Universala grafeo en klaso K de grafeoj estas simpla grafeo en kiu ĉiu ero en K povas esti enigita kiel subgrafeo.

Marŝoj

Marŝo estas alternada vico (sinsekvo) de verticoj kaj lateroj, komenciĝanta kaj finiĝanta ĉe vertico, en kiu ĉiu

vertico estas incida al la du lateroj kiuj antaŭvenas kaj sekvas ĝin en la vico, kaj la verticoj kiuj antaŭvenas kaj

sekvas randon estas la finverticoj de tiu rando. Marŝo estas fermita se ĝia unua kaj lasta verticoj estas la samaj, kaj

malfermita se ili estas malsamaj.

La longeco l de marŝo estas la nombro de lateroj kiujn ĝi uzas. Por malfermita marŝo, l = n–1, kie n estas la nombro

de verticoj vizitis. Por fermita marŝo, l = n (la komenca/fina vertico estas listita dufoje, sed estas ne grafita dufoje).

En la ekzempla grafeo, (1, 2, 5, 1, 2, 3) estas malfermita marŝo kun longeco 5, kaj (4, 5, 2, 1, 5, 4) estas fermita

marŝo de longeco 5.

Spuro estas marŝo en kiu ĉiuj randoj estas distingaj. Fermita spuro jam estas nomita vojaĝo cirkvito, sed ĉi tiuj

estas ne universalaj, kaj la lasta estas ofte rezervita por regula subgrafeo de grado du.

background image

Glosaro de grafeteorio

3

Tradicie, vojo signifas tion kio nun kutime nomatas malfermita marŝo. Nuntempe, kiam komencita sen ia kondiĉo,

vojo estas kutime difinita esti simpla, signifante, ke ĉiu vertico estas incida al maksimume du lateroj. (La termino

ĉeno jam ankaŭ uzatas por nomi marŝon en kiu ĉiuj verticoj (kaj randoj) estas distingaj.) En la ekzempla grafeo, (5,

2, 1) estas vojo de longeco 2. La fermita ekvivalento al ĉi tiu tipo de marŝo estas nomita ciklo. Kiel vojo, ĉi tiu

termino tradicie signifas iun ajn fermitan marŝon, sed nun estas kutime komprenata esti simpla per difino. En la

ekzempla grafeo, (1, 5, 2, 1) estas ciklo de longo 3. (Ciklo, malkiel vojo, estas ne permesita havi longecon 0.) Vojoj

kaj cikloj de n verticoj estas ofte signataj per P

n

kaj C

n

, respektive. (Tamen, iuj aŭtoroj uzas la longon anstataŭ la

nombron de verticoj.)

Ciklo kiu havas neparan longon estas nepara ciklo; alie ĝi estas para ciklo. Unu teoremo estas ke grafeo estas

dupartida grafeo se kaj nur se ne ekzistas ia ajn nepara ciklo. (Vidu en kompleta dupartida grafeo.)

La _girth_ de grafeo estas la longo de plej mallonga (simpla) ciklo en la grafeo; kaj la cirkonferenco, la longo de

plej longa (simpla) ciklo. La _girth_ kaj cirkonferenco de necikla grafeo estas difinita esti malfinio ∞.

Grafeo estas necikla se ĝi enhavas neniujn ciklojn; unucikla se ĝi enhavas ĝuste unu ciklon; kaj pancikla se ĝi

enhavas ciklojn de ĉiu ebla longo (de 3 ĝis la ordo de la grafeo).

C

1

estas ciklo, C

2

estas paro de digonoj (multaj randoj), kaj C

3

estas nomita triangulo.

Vojo aŭ ciklo estas hamiltona (aŭ ampleksanta) se ĝi uzas ĉiujn verticojn ĝuste unufoje. Grafeo kiu enhavas

Hamiltonan vojon estas spurebla; kaj unu kiu enhavas Hamiltonan vojon por iu ajn donita paro de (distingaj)

finverticoj estas hamiltona koneksa grafeo. Grafeo kiu enhavas Hamiltonan ciklon estas Hamiltona grafeo.

Spuro aŭ cirkvito (aŭ ciklo) estas eŭlera se ĝi uzas ĉiujn latetojn precize unufoje. Grafeo kiu enhavas eŭleran spuron

estas trairebla. Grafeo kiu enhavas Eŭleran cirkviton estas eŭlera grafeo. (Vidu ankaŭ en sep pontoj en

Königsberg.)

La ekzempla grafeo ne enhavas eŭleran spuron, sed ĝi ja enhavas Hamiltonan vojon.

Du vojoj estas ene disecaj (iu popolo nomas ĝin sendependa) se ili ne havas ian ajn verticon komune, escepte de la

unuan kaj lastan.

θ-grafeo estas la unio de tri ene disecaj (simplaj) vojoj kiu havas la samajn du klarajn finverticojn. θ

0

grafeo havas

sep verticojn kiuj povas esti aranĝitaj kiel la verticoj de regula sesangulo plus aldona vertico en la centro. La ok

lateroj estas la perimetro de la sesangulo plus unu diametro.

Arboj

arbo estas koneksa necikla simpla grafeo. Vertico de grado 1 estas nomita folio, aŭ penda vertico. Rando incida al

folio estas folia rando, aŭ penda rando. (Iuj homoj difinas folian randon kiel folio kaj tiam difinas folian verticon

super ĝi. Ĉi tiuj du aroj de difinoj estas ofte uzata interŝanĝeble.) Ne-folia vertico estas interna vertico. Fojfoje, unu

vertico de la arbo estas diferencigita, kaj nomita la radiko. Radikigita arbo estas arbo kun radiko. Radikigitaj

arboj estas ofte traktitaj kiel direktitaj neciklaj grafeoj kun la randoj sagantaj foren de la radiko.

Arboj estas kutime uzataj kiel datumstrukturoj en komputiko (vidu arba datumstrukturo).

Subarbo de la arbo A estas koneksa subgrafeo de A.

Arbaro estas vertico-disa unio de arboj; aŭ, ekvivalente, necikla simpla grafeo.

Subarbaro de la arbaro S estas subgrafeo de S.

ampleksanta arbo estas ampleksanta subgrafeo kiu estas arbo. Ĉiu grafeo havas ampleksantan arbaron. Sed nur

koneksa grafeo havas ampleksantan arbon.

Speciala speco de arbo nomita stelo estas K

1,k

. Generita stelo kun 3 randoj estas ungegaro).

k-uma arbo estas radikigita arbo en kiu ĉiu interna vertico havas k infanojn. 1-uma arbo estas simple vojo. 2-uma

arbo estas ankaŭ nomita duuma arbo.

background image

Glosaro de grafeteorio

4

Klikoj

La plena grafeo K

n

de ordo n estas simpla grafeo kun n verticoj en kiu ĉiu vertico estas apuda al ĉiu alia. La

ekzempla grafeo estas ne plena. La plena grafeo sur n verticoj estas ofte signita per K

n

. Ĝi havas n(n-1)/2 randojn

(korespondantajn al ĉiuj eblaj elektoj de paroj de verticoj).

Kliko en grafeo estas aro de duope apudaj verticoj. Ĉar iu ajn subgrafeo generita per kliko estas plena subgrafeo, la

du terminoj kaj ilia notacioj estas kutime uzataj interŝanĝeble. k-kliko estas kliko de ordo k. En la ekzempla grafeo

pli supre, verticoj 1, 2 kaj 5 formas 3-klikon, aŭ triangulon. Maksimuma kliko estas kliko kiu ne estas subaro de ia

alia kliko.

La klika nombro ω(G) de grafeo G estas la ordo de plej granda kliko en G.

Koneksega komponanto

Rilata sed pli malforta koncepto estas tiu de koneksega komponanto. Neformale, koneksega komponanto de grafeo

estas subgrafeo kie ĉiuj verticoj en la subgrafeo estas alireblaj per ĉiuj aliaj verticoj en la subgrafeo. Alirebleco inter

verticoj estas farita de la ekzisto de vojo inter la verticoj.

Orientita grafeo povas esti malkomponita en koneksegajn komponantojn per dufoja rulado de la serĉ-algoritmo

Profundaĵo-unue (en:DFS): unue, super la grafeo mem kaj poste sur la transpono de la grafeo en malkreskanta ordo

de la finado-tempoj de la unua DFS. Donite orientita grafeo G, la transpono G

T

estas la grafeo G kun ĉiu

rando-direktoj renversitaj.

Nodoj

nodo en orientita grafeo estas kolekto de verticoj kaj randoj kun la propraĵo, ke ĉiu vertico en la nodo havas elirajn

randojn, kaj ĉiuj eliraj randoj de verticoj en la nodo havas aliajn verticojn en la nodo kiel celojn. Tial estas neeble

lasi la nodon sekvante la direktojn de la randoj.

Se ĝenerala rimedo grafeo estas celkonforma, tiam nodo estas sufiĉa kondiĉo por (ŝajna?) plenhalto.

(Ĉi tiuj estas tre specialigitaj konceptoj, kiuj estas nekonataj al plej grafeo-teoriistoj.)

Minoroj

Minoro

de

estas injekto de

al

tia, ke ĉiu rando en

korespondas al

vojo (diseca de ĉiuj aliaj tiaj vojoj) en

tia, ke ĉiu vertico en

estas en unu aŭ pli vojoj, aŭ estas parto de la

injekto de

al

. Tio alternative povas esti frazita per termoj de kuntiroj, kiuj estas operacioj kiuj kolapsas vojon

kaj ĉiujn verticojn en ĝi en solan randon (vidu randa kuntiro).

Enigo

Enigo

de

estas injekto de

al

tia, ke ĉiu rando en

korespondas al vojo

(diseca de ĉiuj aliaj tiaj vojoj) en

.

background image

Glosaro de grafeteorio

5

Apudeco kaj grado

En grafeteorio, grado, aparte tiu de vertico, estas kutime mezuro de senpera apudeco.

Rando konektas du verticojn; tiuj du verticoj estas diritaj esti incidaj al tiu rando, aŭ, ekvivalente, tiu rando incidas

al tiuj du verticoj. Ĉiuj al grado rilataj konceptoj koncernas apudecon aŭ incidecon.

La grado, aŭ valento, d

G

(v) de vertico v en grafeo G estas la nombro de randoj incida al v, kun cikloj nombrataj

dufoje. Vertico de grado 0 estas izolita vertico. Vertico de grado 1 estas folio. En la ekzempla grafeo verticoj 1 kaj 3

havas gradon de 2, verticoj 2,4 kaj 5 havas gradon de 3 kaj vertico 6 havas gradon de 1. Se E estas finia, tiam la tuta

sumo de vertico-gradoj estas egala al duoble la nombro de randoj.

Grada vico estas listo de gradoj de grafeo en ne-pligrandiĝanta ordo (ekz. d

1

d

2

≥ … ≥ d

n

). Vico de

ne-pligrandiĝantaj entjeroj estas realigebla se ĝi estas grada vico de iu grafeo.

Du verticoj u kaj v estas konsiderataj apudaj se rando ekzistas inter ili. Ni signigas tion per uv. En la pli supra

grafeo, verticoj 1 kaj 2 estas apudaj, sed verticoj 2 kaj 4 ne. La aro de najbaroj de v, tio estas, verticoj apudaj al v

sed ne inkluzivantaj v mem, formas generitan subgrafeon nomitan (malfermita) najbarejo de v kaj signigitan per

N

G

(v). Kiam v estas ankaŭ inkluzivita, ĝi estas nomita fermita najbaraĵo, signifis per N

G

[v]. Kiam dirita sen ia

kondiĉo, najbarejo estas alprenita esti malfermita. La subindico G estas kutime eliziita kiam estas neniu danĝero de

konfuzo la sama najbareja notacio uzeblas ankaŭ por nome arojn de apudaj verticoj anstataŭ la respektivaj generitaj

subgrafejoj. En la ekzempla grafeo, vertico 1 havas du najbarojn: verticoj 2 kaj 5. Por simpla grafeo, la nombro de

najbaroj, kiun havas vertico koincidas kun ĝia grado.

Dominanta aro de grafeo estas vertica subaro kies fermita najbarejo inkluzivas ĉiujn verticojn de la grafeo. Vertico

v dominas alia verticon u se estas rando de v al u. Vertica subaro V dominas alian vertican subaron U se ĉiu vertico

en U estas najbara al iu vertico en V. La minimuma amplekso de dominanta aro estas la dominada nombro γ(G).

En komputiloj, finia, direktita aŭ nedirektita grafeo (kun n verticoj, ni diru) estas ofte prezentita per ĝia apudeca

matrico: n-per-n matrico kies ĉelo en vico i kaj kolumno j donas la nombron de randoj de la i

-a

ĝis la j

-a

vertico.

Spektra grafeteorio studas interrilatojn inter la propraĵoj de la grafeo kaj ĝia apudeco-matrico.

La maksimuma grado Δ(G) de grafeo G estas la plej granda grado super ĉiuj verticoj; la minimuma grado δ(G), la

plej malgranda.

Grafeo en kiu ĉiu vertico havas la saman gradon estas regula. Ĝi estas k-regula se ĉiu vertico havas gradon k.

0-regula grafeo estas sendependa aro. 1-regula grafeo estas kongruanta. 2-regula grafeo estas vertice diseca unio de

cikloj. 3-regula grafeo nomatas kuba, aŭ trivalenta.

k-faktoro estas k-regula ampleksanta subgrafeo. 1-faktoro estas perfekta kongruanta. Subdisko de randoj de grafeo

en k-faktoroj estas nomita k-faktorigo. k-faktorigebla grafeo estas grafeo, kiu akceptas k-faktorigon.

Grafeo estas biregula se ĝi havas neegalajn maksimuman kaj minimuman gradojn kaj ĉiu vertico havas unun el tiuj

du gradoj.

Forte regula grafeo estas regula grafeo tia, ke iuj ajn apudaj verticoj havas la saman nombron de komunaj najbaroj

kiel alia apudaj paroj kaj, ke iuj ajn neapudaj verticoj havas la sama nombro de komunaj najbaroj kiel alia neapudaj

paroj.

Sendependeco

En grafeteorio, la vorto sendependa kutime kunportas la kunsencon de duop-larĝe disa reciproke neapudaj. En ĉi

tiu senco, sendependeco estas formo de senpera neapudeco. Izolita vertico estas vertico ne incida al iaj randoj.

Sendependa aro, aŭ stabila aro, estas aro de izolitaj verticoj, t.e. neniu paro de verticoj interapudas. Ĉar la grafeo

generita de ia ajn sendependa aro estas malplena grafeo, la du terminoj estas kutime uzataj interŝanĝeble. En la

ekzemplo pli supre, verticoj 1, 3, kaj 6 formas sendependan aron; kaj 3, 5, kaj 6 formas alian.

La sendependeca nombro α(G) de grafeo G estas la grando de plej granda sendependa aro de G.

background image

Glosaro de grafeteorio

6

Grafeo povas esti malkomponita en sendependajn arojn en la senco, ke la tuta vertica aro de la grafeo povas esti

dispartigita en duop-larĝe disecajn sendependajn subarojn. Tiaj sendependaj subaroj estas nomitaj partidaj aroj, aŭ

simple partoj.

Grafeo, kiu povas esti malkomponita en du partidajn arojn sed ne malpli estas dupartidaj; tri aroj sed ne malpli,

tripartidaj; k aroj sed ne malpli, k-partidaj; kaj nekonata nombro de aroj, multpartidaj. 1-parta grafeo estas la

sama kiel sendependa aro, aŭ malplena grafeo. 2-parta grafeo estas la sama kiel dupartida grafeo. Grafeo, kiu povas

esti malkomponita en k partidajn arojn estas ankaŭ dirita esti k-kolorigebla.

Kompleta multpartida grafeo estas grafeo en kiu verticoj estas najbaraj se kaj nur se ili apartenas al malsamaj

partidaj aroj. kompleta dupartida grafeo ankaŭ nomiĝas dukliko.

k-partida grafeo estas duonregula grafeo se ĉiu el ĝiaj partidaj aroj havas uniforman gradon; ekvivalentpartida se

ĉiu partida aro havas la saman grandon; kaj balancita k-partida se ĉiu partida aro diferencas en grando per

maksimume 1 de iu ajn alia.

La kongruanta nombro α&primo;(G) de grafeo G estas la grando de plej granda kongruanta, aŭ duop-larĝaj

verticaj disecaj randoj, de G.

Ampleksanta kongruado, ankaŭ nomita perfekta kongruado estas kongruantaĵo, kiu kovras ĉiujn verticojn de

grafeo).

Konekteco

Konekteco etendas la koncepton de apudo kaj esence estas formo (kaj mezuro) de seria apudeco.

Se estas eble konstati vojon de iu ajn vertico al iu ajn alia vertico de grafeo, la grafeo nomiĝas koneksa; alie, la

grafeo estas malkonektita. Grafeo estas tute malkonektita se estas neniu vojo konektanta ian paron de verticoj. Ĉi

tiu estas nur alia nomo por priskribi malplenan grafeon aŭ sendependan aron.

Tranĉa vertico, aŭ artika punkto), estas vertico kies forigo malkonektas grafeon. Tranĉi aro, aŭ vertica tranĉo

apartiĝanta aro, estas aro de verticoj kies forigo malkonektas la restan grafeon. Ponto estas analoga rando (vidu pli

sube).

Se estas ĉiam eble konstati vojon de iu ajn vertico al ĉiu alia eĉ post forpreno de iuj ajn k - 1 verticoj, tiam la grafeo

estas dirita esti k-koneksa. Notu, ke grafeo estas k-koneksa se kaj nur se ĝi enhavas k ene disecajn vojojn inter iuj

ajn du verticoj. La ekzempla grafeo pli supre estas koneksa (kaj pro tio 1-koneksa), sed ne 2-koneksa. La konekteco

κ(G) de grafeo G estas la minimuma nombro de verticoj bezonataj por malkonekti G. Per konvencio, K

n

havas

konektecon n - 1; kaj malkonektita grafeo havas konektecon 0.

Ponto, aŭ tranĉa rando istmo, estas rando kies forigo malkonektas grafeon. (Ekzemple, arbo estas farita tute el

pontoj.) Malkonektanta aro estas aro de randoj kies forigo pligrandiĝas la nombron de komponantoj. Randa

tranĉo estas la aro de ĉiuj randoj havantaj unu finvertico en iu pozitiva vertica subaro S kaj alia finvertico en V(G)\S.

Randoj de K

3

formas malkonektantan aron, sed ne randan tranĉon. Iuj ajn du randoj de K

3

formas minimuman

malkonektantan aron kaj ankaŭ randan tranĉon. Randa tranĉo laŭnecese estas malkonektanta aro; kaj minimuma

malkonektanta aro de nemalplena grafeo laŭnecese estas randa tranĉo. Ligo estas malgranda (sed ne necese

minimuma), nemalplena aro de randoj kies forigo malkonektas grafeon. Tranĉa vertico estas analoga vertico (vidu

pli supre).

Grafeo estas k-rando-koneksa se iu ajn subgrafeo formita per forpreno de iuj ajn k - 1 randoj estas ankoraŭ koneksa.

La randa konekteco κ&primo;(G) de grafeo G estas la minimuma nombro de randoj bezonataj por malkonekti G.

Unu konata rezulto estas ke κ(G) ≤ κ&primo;(G) ≤ δ(G).

Komponanto estas maksimume koneksa subgrafeo; bloko, ĉu maksimume 2-koneksa subgrafeo aŭ ponto kun ĝiaj

finverticoj; kaj dukoneksa komponanto estas maksimuma aro de randoj en kiu iuj ajn du membroj kuŝas sur

komuna simpla ciklo.

background image

Glosaro de grafeteorio

7

Apartiga vertico de grafeo estas vertico kis forigo el la grafeo pliigas ties nombron de konektitaj komponantoj.

Dukoneksa komponanto difineblas kiel subgrafeo generita de maksimuma aro de nodoj kiu havas neniun apartigan

verticon.

Distanco

La distanco d

G

(u, v) inter du (ne necese distingaj) verticoj u kaj v en grafeo G estas la longeco de la plej mallonga

vojo inter ili. La suba indico G estas kutime eliziita kiam estas neniu danĝero de konfuzo. Kiam u kaj v estas identaj,

ilia distanco estas 0. Kiam u kaj v estas neatingeblaj unu de la alian, ilia distanco estas difinita esti malfinio ∞.

La (discentreco, fokusdiseco) ε

G

(v) de vertico v en grafeo G estas la maksimuma distanco de v al iu ajn alia vertico.

La diametro diam(G) de grafeo G estas la maksimuma (discentreco, fokusdiseco) super ĉiuj verticoj en grafeo; kaj

la radiuso rad(G), la minimuma. Kiam estas du komponantoj en G, tiam diam(G) kaj rad(G) estas difinitaj esti

malfinio ∞. Bagatele, diam(G) ≤ 2 rad(G). Verticoj kun maksimuma (discentreco, fokusdiseco) estas nomitaj

periferiaj verticoj. Verticoj de minimuma (discentreco, fokusdiseco) formas la centron. Arbo havas maksimume du

centrajn verticojn.

La indekso de vertico de Wiener v en grafeo G, signigita per W

G

(v) estas la sumo de distancoj inter v kaj ĉiuj aliaj.

La Wiener-a indekso de grafeo G, signigita per W(G), estas la sumo de distancoj super ĉiuj paroj de verticoj.

Nedirektita grafea Wiener-a polinomo estas difinita esti Σ q

d(u,v)

super ĉiuj neordigitaj paroj de verticoj u kaj v.

Wiener-a indekso kaj Wiener-a polinomo estas de aparta intereso al matematikaj kemiistoj.

La k

-a

potenco G

k

de grafeo G estas supergrafeo formita per aldono de rando inter ĉiuj paroj de verticoj de G kun

distanco maksimume k. Dua potenco de grafeo estas ankaŭ nomita kvadrato.

La k-ampleksanto estas ampleksanta subgrafeo en kiu ĉiuj du verticoj estas maksimume k-oble foraj unu de la alia

sur S ol sur G. La nombro k estas la _dilation_. k-ampleksanto estas uzata por studi geometrian retan optimumigon.

Genro

Kruciĝo estas paro de intertransaj randoj. Grafeo estas enigebla sur surfaco se siaj verticoj kaj randoj povas esti

aranĝitaj sur ĝi sen ia kruciĝo. La genro de grafeo estas la (plej malalta, plej suba) genro de iu ajn surfaco sur kiu la

grafeo povas eniĝi.

Ebeneca grafeo estas tiu kiu povas esti desegnita sur la (Eŭklida) ebeno sen ia kruciĝo; kaj ebeno-grafeo, tiu kiu

estas desegnita en tia maniero. En aliaj vortoj, ebeneca grafeo estas grafeo de genro 0. La ekzempla grafeo estas

ebeneca; la plena grafeo sur n verticoj, por n> 4, estas ne ebeneca. Ankaŭ, arbo laŭnecese estas ebeneca grafeo.

Kiam grafeo estas desegnita sen ia kruciĝo, iu ajn ciklo kiu ĉirkaŭbaras regionon sen ke ia rando atingus el la ciklo

ĝis tia regiono formas edron. Du edroj sur ebeno-grafeo estas najbaraj se ili komunhavas komunan randon. Duala,

ebeneca duala kiam la ĉirkaŭteksto bezonas esti klarigita, G

*

de ebeno-grafeo G estas grafeo kies verticoj

prezentas la edrojn, inkluzivanta iu ajn ekstera edro, de G kaj estas apudaj en G

*

se kaj nur se iliaj respektivaj edroj

estas apudaj en G. La dualo de ebeneca grafeo ĉiam estas ebeneca pseŭdografeo (ekz. konsideru la dualon de

triangulo). En la familiara kazo de 3-koneksa simpla ebeneca grafeo G (izomorfia al konveksa pluredro P), la duala

G

*

estas ankaŭ 3-koneksa simpla ebeneca grafeo (kaj izomorfia al la duala pluredro P

*

).

Aldone, ĉar ni povas konstatigi sencon de "eno" kaj "ekstero" sur ebeno, ni povas identigi "plej eksteran" regionon,

kiu enhavas la tutan grafeo se la grafeo ne kovras la tutan ebenon. Tia plej ekstera regiono estas nomita ekstera edro

. eksterebeniva grafeo) estas unu kiu povas esti desegnita en la ebeneca maniero tia, ke ĝiaj verticoj estas ĉiuj

apudaj al la ekstera edro; kaj eksterebena grafeo, unu kiu ja estas desegnita en tia maniero.

La minimuma nombro de kruciĝoj kiu devas aperi kiam grafeo estas desegnita sur ebeno estas nomita la kruciĝa

nombro.

La minimuma nombro de ebenecaj grafeoj bezonataj por kovri grafeon estas la dikeco de la grafeo.

background image

Glosaro de grafeteorio

8

Pezitaj grafeoj kaj retoj

Pezigita grafeo asociigas etikedan markon (pezo) kun ĉiu rando en la grafeo. Pezoj estas kutime reelaj nombroj. Ili

povas esti limigitaj al racionalaj nombroj aŭ entjeroj. Certaj algoritmoj postulas pliajn limigojn al pezoj; ekzemple, la

Dijkstra-algoritmo funkcias ĝuste nur por pozitivaj pezoj. La pezo de vojo aŭ la pezo arba en pezita grafeo estas la

sumo de la pezoj de la elektitaj randoj. Fojfoje ne-rando estas markita per speciala pezo prezentanta malfinion.

Fojfoje la vorto kosto estas uzata anstataŭ pezo. Kiam dirita sen ia kondiĉo, grafeo estas ĉiam alprenita esti nepezita.

En iuj skriboj pri grafeteorio la termino reto estas sinonimo por pezigita grafeo. Reto povas esti direktita aŭ

nedirektita, ĝi povas enhavi specialajn verticojn (nodojn), kiel fonto dreno. La klasika reto-problemoj inkluzivas:

minimum-kosta ampleksanta arbo,

plej mallonga vojo,

maksimuma fluo (kaj la maksimum-flua minimum-tranĉa teoremo)

Direkto

Arko, aŭ direktita rando, estas ordigita duopo de finverticoj. En tia ordigita duopo, la unua vertico estas nomita

kapo, aŭ komenca vertico; kaj la dua, vosto, aŭ fina vertico. Ĝi povas esti kosiderata rando asociita kun direkto,

nome atribuanta kapon kaj voston al la finverticoj. Nedirektita rando malobservas ian ajn sencon de direkto kaj

traktas ambaŭ finverticojn interŝanĝeble. Ciklo en (orientita grafeo, duliteraĵo), tamen, konservas sencon de direkto

kaj traktas kaj kapon kaj voston idente. Aro de arkoj estas multoblaj, aŭ paralelaj, se ili komunhavas la saman

kapon kaj la saman voston. Paro de arkoj estas kontraŭ-paralelaj se la kapo/vosto de iu estas la vosto/kapo de la

alia. Digrafeo duliteraĵo, aŭ orientita grafeo, estas analoga al nedirektita grafeo escepte de ke ĝi enhavas nur

arkojn. Miksita grafeo povas enteni kaj orientitajn kaj neorientitajn grafeojn. Kiam dirita sen ia kondiĉo, grafeo

estas preskaŭ ĉiam alprenita esti nedirektita. Ankaŭ, (orientita grafeo, duliteraĵo) estas kutime alprenita enhavi ne

nedirektitajn randojn.

(Orientita grafeo, Duliteraĵo) estas nomita simpla se ĝi havas neneiajn ciklojn kaj maksimume unu arkon inter iu ajn

paro de verticoj. Kiam dirita sen ia kondiĉo, (orientita grafeo, duliteraĵo) estas kutime alprenita esti simpla.

En (orientita grafeo, duliteraĵo) Γ, ni (distingi, diferencigi) la eliran gradon d

Γ+

(v), la nombron de randoj lasantaj

verticon v, disde la eniran gradon d

Γ-

(v), la nombron de randoj enirantaj verticon v. Se la grafeo estas orientita, la

grado d

Γ

(v) de vertico v estas egala al la sumo de ĝiaj eliraj kaj eniraj gradoj. Kiam la ĉirkaŭteksto estas klara, la

suba indico Γ povas esti eliziita. Maksimumaj kaj minimumaj eliraj gradoj, estas signitaj per Δ

+

(Γ) kaj δ

+

(Γ); kaj

maksimumaj kaj minimumaj eniraj gradoj, per Δ

-

(Γ) kaj δ

-

(Γ).

Elira najbarejo, aŭ posteula aro, N

(v) de vertico v estas la aro de vostoj de arkoj irantaj de v. Simile, enira

najbarejo, aŭ antaŭula aro, N

(v) de vertico v estas la aro de kapoj de arko iranta al en v.

Fonto estas vertico kun enira duongrado 0; kaj profundiĝi, elira duongrado 0.

Vertico v dominas alian verticon u se estas arko de v al u. Vertica subaro S estas elire dominanta se ĉiu vertico ne

en S estas dominita de iu vertico en S; kaj enire dominanta se ĉiu vertico en S estas dominita de iu vertico ne en S.

Kerno estas sendependa elire dominanta aro. (Orientita grafeo, Duliteraĵo) estas kerno-perfekta se ĉiu generita

subdigrafeo (sub-(orientita grafeo, duliteraĵo)) havas kernon.

Eŭlera digrafeo (orientita grafeo, duliteraĵo) estas digrafeo (orientita grafeo, duliteraĵo) kun egalaj eniraj kaj eliraj

gradoj je ĉiu vertico.

Orientigo estas asigno de direktoj al la randoj de neorientita aŭ parte orientita grafeo. Kiam dirita sen ia kondiĉo,

estas kutime alprenite, ke ĉiuj nedirektitaj randoj estas anstataŭigitaj per direktita en ia orientiĝo. Ankaŭ, la

subkuŝanta grafeo estas kutime alprenita esti nedirektita kaj simpla.

turniro estas digrafeo (orientita grafeo, duliteraĵo) en kiu ĉiu paro de verticoj estas koneksa per ĝuste unu arko. En

aliaj vortoj, ĝi estas orientita plena grafeo.

background image

Glosaro de grafeteorio

9

Direktita vojo, aŭ simple vojo kiam la ĉirkaŭteksto estas klara, estas orientita simpla vojo tia, ke ĉiuj arkoj iras la

saman direkton, kio signifas ke ĉiuj internaj verticoj havas enirajn kaj elirajn duongradojn 1. Vertico v estas

atingebla de alia vertico u se estas direktita vojo, kiu komenciĝas ĉe u kaj finiĝas ĉe v. Notu, ke en ĝeneralo la

kondiĉo, ke u estas atingebla de v ne enhavas, ke v estas ankaŭ atingebla de u.

Se v estas atingebla de u, tiam u estas antaŭulo de v kaj v estas posteulo de u. Se estas arko de u al v, tiam u estas

rekta antaŭulo de v, kaj v estas rekta posteulo de u.

Digrafeo (Orientita grafeo, Duliteraĵo) estas forte koneksa se ĉiu vertico estas atingebla de ĉiu alia sekvante la

direktojn de la arkoj. Kontraŭe, digrafeo estas malforte koneksa se ĝia subkuŝanta nedirektita grafeo estas koneksa.

Malforte koneksa grafeo povas esti konsiderata digrafeo (orientita grafeo, duliteraĵo) en kiu ĉiu vertico estas

"atingebla" de ĉiu alia sed ne necese per sekvado de la direktoj de la arkoj. Forta orientiĝo estas orientiĝo kiu

produktas forte koneksan digrafeon.

Direktita ciklo, aŭ simple ciklo kiam la ĉirkaŭteksto estas klara, estas orientita simpla ciklo tia, ke ĉiuj arkoj iras la

saman direkton, kio signifas ke ĉiuj verticoj havas enirajn kaj elirajn gradojn 1. Digrafeo (Orientita grafeo,

Duliteraĵo) estas necikla se ĝi ne enhavas ian direktitan ciklon. Finia, necikla digrafeo sen izolitaj verticoj laŭnecese

enhavas almenaŭ unu fonton kaj almenaŭ unu drenon. Vidu ankaŭ jenon: direktita necikla grafeo (en:'dag) por pli da

informo.

Arborescenco, aŭ elira arbo (branĉanta, forkiĝanta), estas orientita arbo en kiu ĉiuj verticoj estas atingeblaj de

sola vertico. Simile, en-arbo estas orientita arbo en kiu sola vertico estas atingebla de ĉiu alia.

Diversaj

Grafea invarianto estas propraĵo de grafeo G, kutime nombro aŭ polinomo, kiu dependas nur de la izomorfia klaso

de G. Ekzemploj estas grafeo-ordo, grafeo-genro, kolora nombro, kaj kolora polinomo de la grafeo..

Por esti kunfandita

Notu, ke antaŭ ol la enkonduko de grandaj komputilaj retoj, grafeteorio estis granda kampo sen vasta intereso aŭ

apliko. Ĉar reta analitiko jam iĝas vitala komerca intereso, ne-kleruloj estas priamasintaj la kampon kaj

popularigantaj certajn terminojn.

grafeo, reto

Abstraktado de interrilatoj inter objektoj. Grafeoj konsistas ekskluzive de verticoj kaj randoj. Ĉiuj

karakterizaĵoj de sistemo estas aŭ eliminitaj aŭ subsumita en ĉi tiujn erojn.

figuro

Videbla bildigo de la abstrakta koncepto de grafeo.

punkto, nodo, vertico

Objektoj ("aĵoj") prezentitaj en grafeo. Ĉi tiuj estas preskaŭ ĉiam bildigitaj kiel rondaj punktoj.

rando, ligo, arko

Interrilatoj prezentitaj en grafeo. Ĉi tiuj estas ĉiam bildigitaj kiel rekta aŭ kurbaj linioj. La termino "arko"

povas esti iluzia.

neidentigita

Verticoj aŭ randoj kiuj estas ne konsideritaj kiel individuoj. Nur la maniero laŭ kiu ili konektiĝas al la cetero

de la grafeo karakterizas neidentigitajn verticojn kaj randojn.

koloro, kolorigita, identigita

Nodoj aŭ randoj kiuj estas konsideritaj kiel individuoj. Kvankam ili povas reale esti bildigitaj en figuroj en

malsamaj koloroj, laborantaj matematikistoj ĝenerale enkrajonas nombrojn aŭ literojn.

background image

Glosaro de grafeteorio

10

nedirektita

Grafeo en kiu ĉiu rando simbolas neordigitan, transitivan interrilaton inter du verticoj. Tiaj randoj estas

bildigitaj kiel simplaj linioj aŭ arkoj.

direktita, digrafeo (orientita grafeo, duliteraĵo)

Grafeo en kiu ĉiu rando simbolas orditan, netransitivan interrilaton inter du verticoj. Tiaj randoj estas bildigitaj

kun sagpinto je unu fino de linio aŭ arko.

nepezigita

Grafeo en kiuj ĉiuj interrilatoj simbolitaj per randoj estas konsideritaj ekvivalentaj. Tiaj randoj estas bildigitaj

kiel simplaj linioj aŭ arkoj.

pezigita rando

Pezigitaj randoj simbolas interrilatojn inter verticoj kiuj estas konsiderataj havi ian valoron, ekzemple,

distanco aŭ lam-tempo. Tiaj randoj estas kutime prinotita per nombro aŭ litero lokita apud la rando.

pezigita vertico

Pezigitaj verticoj ankaŭ havas iun valoron malsaman al sia identigo.

apuda

Du randoj estas apudaj se ili komune havas verticon; du verticoj estas apudaj se ili komune havas randon.

grado

La nombro de randoj kiuj konektas verticon.

regula

Grafeo en kiu ĉiu vertico havas la saman gradon.

kompleta

Grafeo en kiu ĉiu nodo estas ligita al ĉiu alia nodo. Por kompleta digrafeo (orientita grafeo, duliteraĵo), tio

signifas po unu ligo en ĉu direkto (el la du).

raŭto

Vico de randoj kaj verticoj de unu vertico al alia. Iu ajn donita rando aŭ vertico povus esti uzata pli ol unufoje.

vojo

Vojo kiu ne pasas ian ajn randon pli ol unufoje. Se la vojo ne pasas ian verticon pli ol unufoje, ĝi estas simpla

vojo.

koneksa

Se iu vojo ekzistas de ĉiu vertico al ĉiu alia, la grafeo estas koneksa. Notu, ke iuj grafeoj estas ne koneksaj.

Figuro de nekonektita grafeo povas aspekti kiel du aŭ pli nerilatajn figurojn, sed ĉiuj verticoj kaj randoj

montritaj estas konsideritaj kiel unu grafeo.

maŝo, ciklo

Vojo kiu finiĝas ĉe la vertico ĉe kiu ĝi komenciĝas.

arbo

Koneksa grafeo sen cikloj.

simpleca vertico

Vertico v estas simpleca se ĉiuj ĝiaj najbaroj estas interkonektitaj. Iu ajn aro de konektitaj simpleca verticoj

formas klikon.

Eŭlera vojo

background image

Glosaro de grafeteorio

11

Vojo kiu pasas tra ĉiu rando (unufoje kaj nur unufoje). Se la komenca kaj fina verticoj estas la samaj, ĝi estas

Eŭlera ciklo Eŭlera cirkvito. Se la komenca kaj fina verticoj estas malsamaj, ĝi estas Eŭlero spuro.

Hamiltona vojo

Vojo kiu pasas tra ĉiu vertico unufoje kaj nur unufoje. Se la komenca kaj fina verticoj estas apudaj, ĝi estas

Hamiltona ciklo.

Vidu ankaŭ jenon:

Grafeo (matematiko)

Grafeteorio

Listo de grafeteoriaj temoj

Bibliografio

Angle

• Bollobás, Béla (1998). Modern Graph Theory ~Moderna Grafeo Teorio. (Novjorko, NY): Springer-Verlag. ISBN

0-387-98488-7. [Pakita kun plibonigitaj temoj sekvis per historia ĝenerala priskribo je la fino de ĉiu ĉapitro.]

Diestel, Reinhard (2005), "Graph Theory, Third Edition". Springer. ISBN 3-540-26182-6 ["Standard textbook,

most basic material and some deeper results, exercises of various difficulty and notes at the end of each chapter;

known for being quasi error-free."]

• West, Duglaso B. (2001). Introduction to Graph Theory ~Enkonduko al Grafeo Teorio (2ed). Upper Saddle

River: Prentice Hall;. ISBN 0-13-014400-2. [Tunoj de ilustraĵoj, referencoj, kaj ekzercas. La plej kompleta

komencdira gvidilo al la subjekto.]

• Eriko W. Weisstein. "Graph." ~Grafeo. De MathWorld--A Wolframo Web Resource. http:/

/

mathworld.

wolfram.

com/

Graph.

html

• Zaslavsky, Tomaso. "Glossary of signed and gain graphs and allied areas. ~Glosaro de signitaj kaj gajnaj grafeoj

kaj aliancanitaj areoj. Elektronika Ĵurnalo de Kombinatoriko, Dinamikaj Katastroj en Kombinatoriko, # DS 8.

http:/

/

www.

kombinatoriko.

org/

Katastroj/

background image

Artikolaj fontoj kaj kontribuantoj

12

Artikolaj fontoj kaj kontribuantoj

Glosaro de grafeteorio  Fonto: http://eo.wikipedia.org/w/index.php?oldid=2566890  Kontribuantoj: Alaŭdo, Maksim, Oryanw, UNiesert

Bildaj fontoj, licencoj kaj kontribuantoj

Dosiero:6n-graf.png  Fonto: http://eo.wikipedia.org/w/index.php?title=Dosiero:6n-graf.png  Permesilo: Public Domain  Kontribuantoj: en:User:Chmod007

Permesilo

Creative Commons Attribution-Share Alike 3.0 Unported
//creativecommons.org/licenses/by-sa/3.0/


Document Outline


Wyszukiwarka

Podobne podstrony:
Glosario de Semana Santa
Glosario de teoría de categorías
Glosario de Semana Santa
Glosario de teoría de categorías
Glosario de la geometría de Riemann
Glosario de heráldica
Glosario de términos artilleros
Glosario de terminología musical
Glosario de términos médicos
Glosario de topología
Glosario de baloncesto
Glosario de anime y manga
Glosario de teoría de grafos
Glosario de boxeo
Glosario de relatividad
Brasil Política de 1930 A 2003

więcej podobnych podstron