Glosaro de grafeteorio.pdf
(
135 KB
)
Pobierz
(anonymous)
Glosaro de grafeteorio
1
Glosaro de grafeteorio
Grafeteorio e
stas kreska areo en
matematika e
splorado, 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
aŭ
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 s
uper 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
x
⋅
y
). 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
e
stas 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
aŭ
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
k
utime 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.
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
aŭ
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
e
stas 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
aŭ
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
s
ignifas 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).
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 p
lus aldona vertico en la centro. La ok
lateroj estas la perimetro de la sesangulo plus unu diametro.
Arboj
arbo
e
stas 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
e
stas 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
.
C
1
estas
ciklo
,
C
2
estas paro de
digonoj
(multaj randoj), kaj
C
3
estas nomita
triangulo
.
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
e
n 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 e
stas 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 d
e 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
.
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.
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
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
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
s
tudas 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
aŭ
reciproke neapudaj
. En ĉi
tiu senco, sendependeco estas formo de
senpera neapudeco
.
Izolita vertico
e
stas 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
.
Grada vico
estas listo de gradoj de grafeo en ne-pligrandiĝanta ordo (ekz.
d
1
≥
d
2
≥ … ≥
d
n
). Vico de
Plik z chomika:
zkliban
Inne pliki z tego folderu:
Terminaro de klasika dancado.pdf
(5286 KB)
Glosaro de grafeteorio.pdf
(135 KB)
Listo de sendependaj ŝtatoj.pdf
(172 KB)
Listo de kemiaj elementoj laŭ nomo.pdf
(92 KB)
Inne foldery tego chomika:
epo esperanto
Esperanto
ESPERANTO (LINGWISTYKA)
Kurs Esperanto
Maria Niemirow, Esperanto dla wszystkich
Zgłoś jeśli
naruszono regulamin