Glosaro de grafeteorio
1
Glosaro de grafeteorio
Grafeteorio estas kreska areo en matematika esplorado, kaj havas grandan fakan vortoprovizon. Kelkaj am
toroj uzas
la saman vorton kun malsamaj signifoj. Aliaj am
toroj uzas malsamajn vortojn celante la saman aferon. 
i tiu pa%1ńo
provizas la superrigardon pri nuntempa terminaro de grafeteorio kaj provas teni sin lam
eble %1ńisdatigita kun la aktuala
lingvouzo.
Fundamenta5
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 am
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 %1ńiaj finpunktoj.
Randoj povas esti dotitaj kun direkto, kondukante al la nocio de orientita grafeo am
dulitera5
o, vidu sekcion
#Direkto.
Alternativaj modeloj de grafeo ekzistas; ekz., grafeo povas esti konsiderata kiel Bulea duuma funkcio super la aro de
verticoj am
kiel kvadrata (0,1)-matrico.
Vertico (baza ero) estas simple desegnita kiel punkto. La vertica aro de G estas kutime signita de V(G), am
V kiam
estas neniu dan%1ńero de konfuzo. La ordo de grafeo estas la nombro de %1ńiaj verticoj, kio estas |V(G)|.
Latero (aro de du eroj) estas desegnita kiel linio konektanta du verticojn, nomitajn finverticoj, am
finpunktoj. Rando
kun finverticoj x kaj y estas signata per xy (sen ia ajn simbolo en intere, do, ne skribu x�"y). La rando-aro de G estas
kutime signata per E(G), am
E kiam estas neniu dan%1ń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 %1ń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 %1ńiaj lateroj. Grafeo estas
simpla grafeo se %1ńi havas neniun multoblan lateron nek multoblan ciklon, plurgrafeo se %1ńi havas multoblajn
laterojn, sed ne ciklojn, kaj plurgrafeo am
psem
dografeo se %1ńi enhavas kaj multoblajn laterojn kaj ciklojn (la
literaturo estas alte nekonsekvenca). Kiam dirite sen ia kondi
o, grafeo estas preskam

iam alprenita esti simpla  am

oni devas ju%1ńi lam
la
irkam
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 am
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 am
lateraj aroj
unuflanke, kaj izomorfiaj tipoj am
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.
Glosaro de grafeteorio
2
Kontram
-latero estas latero, kiu "estas ne tie". Pli formale, por du verticoj u kaj v, {u, v} estas kontram
-latero en
grafeo G se (u, v) ne estas latero en G. 
i tio signifas, ke ne estas latero inter la du verticoj am
estas nur latero (v, u)
de v al u se G estas direktita.
Kontram
-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 am
malplena grafeo estas grafeo eble kun iuj verticoj, sed sen lateroj. Am
, %1ńi estas
grafeo sen verticoj kaj sen lateroj.
La nula grafeo estas la grafeo sen verticoj kaj sen lateroj. Am
, %1ńi estas grafeo sen lateroj kaj ia nombro de
verticoj, en kiu kazo %1ńi povas nomi%1ńi la nula grafeo sur verticoj. (Estas nenia ajn konsekvenceco en la
literaturo.)
Grafeo estas malfinia se %1ńi havas malfinie multajn verticojn am
randojn am
ambam
; 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, dissur5
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 sur5
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 am
estas izomorfia al H (depende de la bezonoj de la situacio).
Subgrafeo H estas ampleksanta subgrafeo, am
faktoro, de grafeo G se %1ń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 %1ń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%5ńoj
Mar%5ńo estas alternada vico (sinsekvo) de verticoj kaj lateroj, komenci%1ńanta kaj fini%1ńanta
e vertico, en kiu
iu
vertico estas incida al la du lateroj kiuj antam
venas kaj sekvas %1ńin en la vico, kaj la verticoj kiuj antam
venas kaj
sekvas randon estas la finverticoj de tiu rando. Mar%5ńo estas fermita se %1ńia unua kaj lasta verticoj estas la samaj, kaj
malfermita se ili estas malsamaj.
La longeco l de mar%5ńo estas la nombro de lateroj kiujn %1ńi uzas. Por malfermita mar%5ńo, l = n 1, kie n estas la nombro
de verticoj vizitis. Por fermita mar%5ń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%5ńo kun longeco 5, kaj (4, 5, 2, 1, 5, 4) estas fermita
mar%5ńo de longeco 5.
Spuro estas mar%5ńo en kiu
iuj randoj estas distingaj. Fermita spuro jam estas nomita voja%1ńo am
cirkvito, sed
i tiuj
estas ne universalaj, kaj la lasta estas ofte rezervita por regula subgrafeo de grado du.
Glosaro de grafeteorio
3
Tradicie, vojo signifas tion kio nun kutime nomatas malfermita mar%5ń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 ankam
uzatas por nomi mar%5ń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%5ńo estas nomita ciklo. Kiel vojo,
i tiu
termino tradicie signifas iun ajn fermitan mar%5ń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 Pn kaj Cn, respektive. (Tamen, iuj am
toroj uzas la longon anstatam
la
nombron de verticoj.)
Ciklo kiu havas neparan longon estas nepara ciklo; alie %1ń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 %1ńi enhavas neniujn ciklojn; unucikla se %1ńi enhavas %1ńuste unu ciklon; kaj pancikla se %1ńi
enhavas ciklojn de
iu ebla longo (de 3 %1ńis la ordo de la grafeo).
C1 estas ciklo, C2 estas paro de digonoj (multaj randoj), kaj C3 estas nomita triangulo.
Vojo am
ciklo estas hamiltona (am
ampleksanta) se %1ńi uzas
iujn verticojn %1ń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 am
cirkvito (am
ciklo) estas em
lera se %1ńi uzas
iujn latetojn precize unufoje. Grafeo kiu enhavas em
leran spuron
estas trairebla. Grafeo kiu enhavas Em
leran cirkviton estas em
lera grafeo. (Vidu ankam
en sep pontoj en
K�nigsberg.)
La ekzempla grafeo ne enhavas em
leran spuron, sed %1ńi ja enhavas Hamiltonan vojon.
Du vojoj estas ene disecaj (iu popolo nomas %1ń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%1ń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, am
penda vertico. Rando incida al
folio estas folia rando, am
penda rando. (Iuj homoj difinas folian randon kiel folio kaj tiam difinas folian verticon
super %1ńi. 
i tiuj du aroj de difinoj estas ofte uzata inter%5ńan%1ń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; am
, 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 K1,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 ankam
nomita duuma arbo.
Glosaro de grafeteorio
4
Klikoj
La plena grafeo Kn 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 Kn. 
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%5ńan%1ńeble. k-kliko estas kliko de ordo k. En la ekzempla grafeo
pli supre, verticoj 1, 2 kaj 5 formas 3-klikon, am
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
Profunda5
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 GT estas la grafeo G kun
iu
rando-direktoj renversitaj.
Nodoj
nodo en orientita grafeo estas kolekto de verticoj kaj randoj kun la propra5
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 %1ńenerala rimedo grafeo estas celkonforma, tiam nodo estas sufi
a kondi
o por (%5ń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 am
pli vojoj, am
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 %1ń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 .
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, am
, ekvivalente, tiu rando incidas
al tiuj du verticoj. 
iuj al grado rilataj konceptoj koncernas apudecon am
incidecon.
La grado, am
valento, dG(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%1ńanta ordo (ekz. d1 e" d2 e" & e" dn). Vico de
ne-pligrandi%1ńantaj entjeroj estas realigebla se %1ńi estas grada vico de iu grafeo.
Du verticoj u kaj v estas konsiderataj apudaj se rando ekzistas inter ili. Ni signigas tion per u �! v. 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
NG(v). Kiam v estas ankam
inkluzivita, %1ńi estas nomita fermita najbara5
o, signifis per NG[v]. Kiam dirita sen ia
kondi
o, najbarejo estas alprenita esti malfermita. La subindico G estas kutime eliziita kiam estas neniu dan%1ńero de
konfuzo la sama najbareja notacio uzeblas ankam
por nome arojn de apudaj verticoj anstatam
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 %1ń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 am
nedirektita grafeo (kun n verticoj, ni diru) estas ofte prezentita per %1ńia apudeca
matrico: n-per-n matrico kies
elo en vico i kaj kolumno j donas la nombron de randoj de la i-a %1ńis la j-a vertico.
Spektra grafeteorio studas interrilatojn inter la propra5
oj de la grafeo kaj %1ń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, am
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 %1ń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%1ńe disa am
reciproke neapudaj. En
i
tiu senco, sendependeco estas formo de senpera neapudeco. Izolita vertico estas vertico ne incida al iaj randoj.
Sendependa aro, am
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%5ńan%1ń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.
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%1ńe disecajn sendependajn subarojn. Tiaj sendependaj subaroj estas nomitaj partidaj aroj, am

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, am
malplena grafeo. 2-parta grafeo estas la sama kiel dupartida grafeo. Grafeo, kiu povas
esti malkomponita en k partidajn arojn estas ankam
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 ankam
nomi%1ńas dukliko.
k-partida grafeo estas duonregula grafeo se
iu el %1ń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, am
duop-lar%1ńaj
verticaj disecaj randoj, de G.
Ampleksanta kongruado, ankam
nomita perfekta kongruado estas kongruanta5
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%1ń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 am
sendependan aron.
Tran
a vertico, am
artika punkto), estas vertico kies forigo malkonektas grafeon. Tran
i aro, am
vertica tran
o am

aparti%1ń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 %1ń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, Kn havas
konektecon n - 1; kaj malkonektita grafeo havas konektecon 0.
Ponto, am
tran
a rando am
istmo, estas rando kies forigo malkonektas grafeon. (Ekzemple, arbo estas farita tute el
pontoj.) Malkonektanta aro estas aro de randoj kies forigo pligrandi%1ń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 K3 formas malkonektantan aron, sed ne randan tran
on. Iuj ajn du randoj de K3 formas minimuman
malkonektantan aron kaj ankam
randan tran
on. Randa tran
o lam
necese estas malkonektanta aro; kaj minimuma
malkonektanta aro de nemalplena grafeo lam
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 ankoram
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) d" �&primo;(G) d" �(G).
Komponanto estas maksimume koneksa subgrafeo; bloko,
u maksimume 2-koneksa subgrafeo am
ponto kun %1ńiaj
finverticoj; kaj dukoneksa komponanto estas maksimuma aro de randoj en kiu iuj ajn du membroj ku%5ńas sur
komuna simpla ciklo.
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 dG(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%1ń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) d" 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 WG(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 Ł qd(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 Gk 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 ankam
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%1ńo estas paro de intertransaj randoj. Grafeo estas enigebla sur surfaco se siaj verticoj kaj randoj povas esti
aran%1ńitaj sur %1ńi sen ia kruci%1ńo. La genro de grafeo estas la (plej malalta, plej suba) genro de iu ajn surfaco sur kiu la
grafeo povas eni%1ńi.
Ebeneca grafeo estas tiu kiu povas esti desegnita sur la (Em
klida) ebeno sen ia kruci%1ń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. Ankam
, arbo lam
necese estas ebeneca grafeo.
Kiam grafeo estas desegnita sen ia kruci%1ńo, iu ajn ciklo kiu
irkam
baras regionon sen ke ia rando atingus el la ciklo
%1ńis tia regiono formas edron. Du edroj sur ebeno-grafeo estas najbaraj se ili komunhavas komunan randon. Duala,
am
ebeneca duala kiam la
irkam
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 psem
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 ankam
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 %1ń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%1ńoj kiu devas aperi kiam grafeo estas desegnita sur ebeno estas nomita la kruci%1ńa
nombro.
La minimuma nombro de ebenecaj grafeoj bezonataj por kovri grafeon estas la dikeco de la grafeo.
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 am
entjeroj. Certaj algoritmoj postulas pliajn limigojn al pezoj; ekzemple, la
Dijkstra-algoritmo funkcias %1ńuste nur por pozitivaj pezoj. La pezo de vojo am
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 anstatam
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 am

nedirektita, %1ńi povas enhavi specialajn verticojn (nodojn), kiel fonto am
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, am
direktita rando, estas ordigita duopo de finverticoj. En tia ordigita duopo, la unua vertico estas nomita
kapo, am
komenca vertico; kaj la dua, vosto, am
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 ambam
finverticojn inter%5ńan%1ńeble. Ciklo en (orientita grafeo, dulitera5
o), tamen, konservas sencon de direkto
kaj traktas kaj kapon kaj voston idente. Aro de arkoj estas multoblaj, am
paralelaj, se ili komunhavas la saman
kapon kaj la saman voston. Paro de arkoj estas kontram
-paralelaj se la kapo/vosto de iu estas la vosto/kapo de la
alia. Digrafeo am
dulitera5
o, am
orientita grafeo, estas analoga al nedirektita grafeo escepte de ke %1ńi enhavas nur
arkojn. Miksita grafeo povas enteni kaj orientitajn kaj neorientitajn grafeojn. Kiam dirita sen ia kondi
o, grafeo
estas preskam

iam alprenita esti nedirektita. Ankam
, (orientita grafeo, dulitera5
o) estas kutime alprenita enhavi ne
nedirektitajn randojn.
(Orientita grafeo, Dulitera5
o) estas nomita simpla se %1ńi havas neneiajn ciklojn kaj maksimume unu arkon inter iu ajn
paro de verticoj. Kiam dirita sen ia kondi
o, (orientita grafeo, dulitera5
o) estas kutime alprenita esti simpla.
En (orientita grafeo, dulitera5
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 %1ńiaj eliraj kaj eniraj gradoj. Kiam la
irkam
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, am
posteula aro, N+ (v) de vertico v estas la aro de vostoj de arkoj irantaj de v. Simile, enira
�
najbarejo, am
antam
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%1ń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, Dulitera5
o) estas kerno-perfekta se
iu generita
subdigrafeo (sub-(orientita grafeo, dulitera5
o)) havas kernon.
Em
lera digrafeo (orientita grafeo, dulitera5
o) estas digrafeo (orientita grafeo, dulitera5
o) kun egalaj eniraj kaj eliraj
gradoj je
iu vertico.
Orientigo estas asigno de direktoj al la randoj de neorientita am
parte orientita grafeo. Kiam dirita sen ia kondi
o,
estas kutime alprenite, ke
iuj nedirektitaj randoj estas anstatam
igitaj per direktita en ia orienti%1ńo. Ankam
, la
subku%5ńanta grafeo estas kutime alprenita esti nedirektita kaj simpla.
turniro estas digrafeo (orientita grafeo, dulitera5
o) en kiu
iu paro de verticoj estas koneksa per %1ńuste unu arko. En
aliaj vortoj, %1ńi estas orientita plena grafeo.
Glosaro de grafeteorio
9
Direktita vojo, am
simple vojo kiam la
irkam
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%1ńas
e u kaj fini%1ńas
e v. Notu, ke en %1ńeneralo la
kondi
o, ke u estas atingebla de v ne enhavas, ke v estas ankam
atingebla de u.
Se v estas atingebla de u, tiam u estas antam
ulo de v kaj v estas posteulo de u. Se estas arko de u al v, tiam u estas
rekta antam
ulo de v, kaj v estas rekta posteulo de u.
Digrafeo (Orientita grafeo, Dulitera5
o) estas forte koneksa se
iu vertico estas atingebla de
iu alia sekvante la
direktojn de la arkoj. Kontram
e, digrafeo estas malforte koneksa se %1ńia subku%5ńanta nedirektita grafeo estas koneksa.
Malforte koneksa grafeo povas esti konsiderata digrafeo (orientita grafeo, dulitera5
o) en kiu
iu vertico estas
"atingebla" de
iu alia sed ne necese per sekvado de la direktoj de la arkoj. Forta orienti%1ńo estas orienti%1ńo kiu
produktas forte koneksan digrafeon.
Direktita ciklo, am
simple ciklo kiam la
irkam
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,
Dulitera5
o) estas necikla se %1ńi ne enhavas ian direktitan ciklon. Finia, necikla digrafeo sen izolitaj verticoj lam
necese
enhavas almenam
unu fonton kaj almenam
unu drenon. Vidu ankam
jenon: direktita necikla grafeo (en:'dag) por pli da
informo.
Arborescenco, am
elira arbo am
(bran
anta, forki%1ń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 propra5
o de grafeo G, kutime nombro am
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 antam
ol la enkonduko de grandaj komputilaj retoj, grafeteorio estis granda kampo sen vasta intereso am

apliko. 
ar reta analitiko jam i%1ń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
karakteriza5
oj de sistemo estas am
eliminitaj am
subsumita en
i tiujn erojn.
figuro
Videbla bildigo de la abstrakta koncepto de grafeo.
punkto, nodo, vertico
Objektoj ("a5
oj") prezentitaj en grafeo. 
i tiuj estas preskam

iam bildigitaj kiel rondaj punktoj.
rando, ligo, arko
Interrilatoj prezentitaj en grafeo. 
i tiuj estas
iam bildigitaj kiel rekta am
kurbaj linioj. La termino "arko"
povas esti iluzia.
neidentigita
Verticoj am
randoj kiuj estas ne konsideritaj kiel individuoj. Nur la maniero lam
kiu ili konekti%1ńas al la cetero
de la grafeo karakterizas neidentigitajn verticojn kaj randojn.
koloro, kolorigita, identigita
Nodoj am
randoj kiuj estas konsideritaj kiel individuoj. Kvankam ili povas reale esti bildigitaj en figuroj en
malsamaj koloroj, laborantaj matematikistoj %1ńenerale enkrajonas nombrojn am
literojn.
Glosaro de grafeteorio
10
nedirektita
Grafeo en kiu
iu rando simbolas neordigitan, transitivan interrilaton inter du verticoj. Tiaj randoj estas
bildigitaj kiel simplaj linioj am
arkoj.
direktita, digrafeo (orientita grafeo, dulitera5
o)
Grafeo en kiu
iu rando simbolas orditan, netransitivan interrilaton inter du verticoj. Tiaj randoj estas bildigitaj
kun sagpinto je unu fino de linio am
arko.
nepezigita
Grafeo en kiuj
iuj interrilatoj simbolitaj per randoj estas konsideritaj ekvivalentaj. Tiaj randoj estas bildigitaj
kiel simplaj linioj am
arkoj.
pezigita rando
Pezigitaj randoj simbolas interrilatojn inter verticoj kiuj estas konsiderataj havi ian valoron, ekzemple,
distanco am
lam-tempo. Tiaj randoj estas kutime prinotita per nombro am
litero lokita apud la rando.
pezigita vertico
Pezigitaj verticoj ankam
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, dulitera5
o), tio
signifas po unu ligo en
u direkto (el la du).
ram
to
Vico de randoj kaj verticoj de unu vertico al alia. Iu ajn donita rando am
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, %1ń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 am
pli nerilatajn figurojn, sed
iuj verticoj kaj randoj
montritaj estas konsideritaj kiel unu grafeo.
ma%5ńo, ciklo
Vojo kiu fini%1ńas
e la vertico
e kiu %1ńi komenci%1ńas.
arbo
Koneksa grafeo sen cikloj.
simpleca vertico
Vertico v estas simpleca se
iuj %1ńiaj najbaroj estas interkonektitaj. Iu ajn aro de konektitaj simpleca verticoj
formas klikon.
Em
lera vojo
Glosaro de grafeteorio
11
Vojo kiu pasas tra
iu rando (unufoje kaj nur unufoje). Se la komenca kaj fina verticoj estas la samaj, %1ńi estas
Em
lera ciklo am
Em
lera cirkvito. Se la komenca kaj fina verticoj estas malsamaj, %1ńi estas Em
lero spuro.
Hamiltona vojo
Vojo kiu pasas tra
iu vertico unufoje kaj nur unufoje. Se la komenca kaj fina verticoj estas apudaj, %1ńi estas
Hamiltona ciklo.
Vidu ankam
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 %1ń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 ilustra5
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 4
urnalo de Kombinatoriko, Dinamikaj Katastroj en Kombinatoriko, # DS 8.
http:/ / www. kombinatoriko. org/ Katastroj/
Artikolaj fontoj kaj kontribuantoj
12
Artikolaj fontoj kaj kontribuantoj
Glosaro de grafeteorio Fonto: http://eo.wikipedia.org/w/index.php?oldid=2566890 Kontribuantoj: Alam
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/