- Ábel azonosság
lásd
1.44.
- Ág
a
G
gráfban az
x
ponthoz tartozó ágaz a
részgráf, mely a
G
−
x
gráf egy
G
1
komponenséből, az
x
pontból és az
x
-et
G
1
-hez kötő élekből áll.
Átmérő (
G
gráfé): a pontok között előforduló
maximális távolság.
- Automorfizmus ([irányított] gráfé)
a
V
(
G
)
olyan
α
permutációja, melyben az
(
x
,
y
)
-élek száma azonos az
(
α
(
x
)
,
α
(
y
)
)
-élek számával
(
x
,
y
∈
V
(
G
)
)
. Beszélhetünk egy színezett élű
G
gráf automorfizmusáról. Ez olyan
α
permutációt jelent, hogy az
(
x
,
y
)
-élek száma azonos az
(
α
(
x
)
,
α
(
y
)
)
-élek számával bármilyen adott színre.
Egy [irányított] gráf összes automorfizmusainak halmaza
egy
A
(
G
)
permutációs csoportot alkot.
- Azonosítás
a
G
[irányított] gráfban az
x
,
y
pontok azonosítása olyan
G
′
[irányított] gráfot eredményez, melyre
V
(
G
′
)
=
V
(
G
)
−
{
x
,
y
}
∪
{
x
y
¯
}
, ahol
z
=
x
y
¯
egy új pontot jelöl,
E
(
G
′
)
=
E
(
G
)
, és minden
e
∈
E
(
G
)
él végpontjai azonosak
G
′
-ben és
G
-ben, kivéve, ha valamelyik végpontja
x
vagy
y
volt, ekkor helyette
x
y
¯
lesz. Ily módon minden
(
x
,
y
)
-él
x
y
¯
-hoz illeszkedő hurokká válik.
- Bell szám
lásd partíció.
- Binomiális együttható
n
k
ahányféleképpen
n
elemből
k
-t kiválaszthatunk. Ezt a számot az
alábbi formula adja meg:
és definíció szerint
Az
(1)formula megadja
n
k
-t bármely valós (vagy komplex)
n
értékre.
- Brooks tétele
lásd
9.13.
- Brun szita
lásd
2.13.
- Burnside lemma
lásd
3.23.
- Catalan számok
lásd
1.33,
1.37–40.
- Cayley formula
lásd
4.2.
- Ciklikus permutáció
azonosítsuk ugyanazon
S
halmaz két
(
x
1
,
…
,
x
n
)
,
(
y
1
,
…
,
y
n
)
rendezését, ha
y
1
=
x
k
+
1
,
…
,
y
n
−
k
=
x
n
,
y
n
−
k
+
1
=
x
1
,
…
,
y
n
=
x
k
valamely
1
≤
k
≤
n
-re. Az így definiált
ekvivalencia-reláció egy osztálya ciklikus permutációt
alkot.
Ciklusszámláló polinom (
Γ
permutációs csoporté): A
polinom, ahol
n
azon elemek száma, melyeken
Γ
fut és
k
i
(
π
)
a
π
permutáció ciklus-felbontásában az
i
hosszúságú ciklusok száma.
- Csillag
olyan fa, melyben egyetlen pont van minden más
ponttal összekötve. Egy pont csillaga:
lásd gráf.
- Csúcs
lásd gráf.
- Csúcsmátrix (
G
gráfé):
az
A
G
=
(
a
i
j
)
i
,
j
=
1
n
mátrix, ahol
V
(
G
)
=
{
v
1
,
…
,
v
n
}
, és
A
i
j
a
(
v
i
,
v
j
)
-élek száma.
- Duális síkgráf
egy összefüggő
G
síkgráf duálisa a következők szerint
konstruált
G
∗
síkgráf. Kiválasztunk egy
x
F
pontot a
G
minden
F
lapján; ezek lesznek
G
∗
pontjai. Kiválasztunk még egy
p
e
pontot is
G
minden
e
élén. Minden
p
e
pontot összekötünk az
x
F
és
x
F
′
pontokkal az
F
ill.
F
′
belsejében haladó
J
e
,
J
e
′
Jordan-görbékkel, ahol
F
,
F
′
az
e
-vel szomszédos két lap. Ha
F
=
F
′
(azaz
G
azonos lapja határolja
e
-t mindkét oldalról), akkor
J
e
-nek és
J
e
′
-nek úgy kell
p
e
-t
x
F
-fel összekötnie, hogy
p
e
-t
e
különböző oldalán hagyják el (ez akkor
fordul elő, ha
e
elvágó-él). Továbbá válasszuk
J
e
,
J
e
′
-t úgy, hogy az
x
F
-et
F
határán lévő
p
e
pontokhoz kötő
J
e
íveknek ne legyen
x
F
-től különböző közös pontjuk. Legyen
e
∗
=
J
e
∪
J
e
′
és
E
(
G
∗
)
=
{
e
∗
:
e
∈
E
(
G
)
}
. Ekkor
G
∗
szintén síkbarajzolható gráf. Ha
G
-t és
G
∗
-ot gömbfelületbe ágyazottnak tekintjük,
akkor a duális síkgráf szükségképpen egyértelműen meg van
határozva, azaz ha
G^
∗
a
G
egy másik duális síkgráfja, akkor
létezik a gömbfelületnek egy saját magára történő
ϕ
homeomorfizmusa, melyre
ϕ
(
x
)
=
x
minden
x
∈
V
(
G
)
esetén,
ϕ
(
e
)
=
e
minden
e
∈
E
(
G
)
esetén,
ϕ
(
V
(
G
∗
)
)
=
V
(
G^
∗
)
, és ha
ê
∗
az
e
∗
-nak megfelelő él
G^
∗
-ban, akkor
ϕ
(
e
∗
)
=
ê
∗
.
G
∗
duálisa
G
. A fenti konstrukció és az utolsó
állítások sokmindent felhasználnak a síktopológiából,
amit mi itt bizonyítás nélkül elfogadunk (120. ábra).
- Edmonds párosítási algoritmusa
lásd
7.34.
- Egyszerű gráf, irányított gráf, hipergráf
lásd gráf,
irányított gráf,
hipergráf.
- Él
lásd gráf,
irányított gráf,
hipergráf.
- Elemi páros gráf
lásd
7.7.
- Elérési idő
lásd véletlen séta.
- Élgráf (
G
[hiper]gráfé):
a következőképpen definiált
L
(
G
)
egyszerű gráf:
(
G
irányított gráf élgráfja): a
következőképpen definiált
L
(
G
)
egyszerű irányított gráf:
- Elhagyás
egy
X
⊆
V
(
G
)
halmaz elhagyása egy
G
[hiper-, irányított] gráfból az
X
összes pontjának elhagyása az összes
hozzájuk illeszkedő éllel együtt. A kapott [hiper-,
irányított] gráf jelölése
G
−
X
; ha
X
=
{
x
}
, jelölése egyszerűen
G
−
x
.
- Élösszefüggés
egy gráf
k
-szorosan élösszefüggő (
k
-élösszefüggő) az
a
és
b
pontjai között, ha bárhogyan is hagyunk
el legfeljebb
k
−
1
élét, a kapott [irányított] gráf
tartalmaz
(
a
,
b
)
-utat. Egy [irányított] gráf
k
-szorosan élösszefüggő, ha bármely két
pontja között az. Ekvivalens megfogalmazásban: ha
bárhogyan is hagyunk el legfeljebb
k
−
1
élét, a kapott [irányított] gráf
[erősen] összefüggő.
- Elvágó halmaz
olyan ponthalmaz [élhalmaz] egy összefüggő gráfban,
melynek elhagyásával a gráf nem-összefüggővé válik.
Elvágó-pont [elvágó-él]:
olyan pont [él], mely önmagában elvágó halmazt alkot.
- Elválasztás
egy pontokból és élekből álló
X
halmaz elválasztja
(
A
,
B
)
-t (
A
,
B
⊆
V
(
G
)
), ha reprezentálja (lefogja) az összes
(
A
,
B
)
-utat (vö. elvágó-halmaz).
- Endomorfizmus
a
G
[irányított] gráf endomorfizmusa egy
saját magába történő homomorfizmusa. A
G
összes endomorfizmusa a kompozícióval
mint szorzással félcsoportot alkot, ennek jelölése
End
(
G
)
.
- Erdő
körmentes gráf. Az erdő komponensei fák.
- Erdős–de Bruijn tétel
lásd
8.14.
- Erdős–Ko–Rado tétel
lásd
13.28.
- Erdős–Stone tétel
lásd
10.38.
- Euler-vonal
a(z) [irányított] gráf minden élét tartalmazó zárt
vonal.
- Euler-féle [irányított]gráf
van benne Euler-vonal.
- Euler formula
lásd
5.24.
- Fa
körmentes összefüggő gráf. Úgy is definiálható,
mint olyan összefüggő gráf, mely bármely éle elhagyásával
nem-összefüggővé válik; vagy mint olyan körmentes gráf,
melyben tetszőleges él felvételével kör keletkezik. Egy
n
pontú fának pontosan
n
−
1
éle van és mindig tartalmaz legalább 2
elsőfokú pontot, feltéve, hogy
∣
V
(
G
)
∣
≥
2
. Gyökeres fa az olyan fa, melyben
kitüntettünk egy pontot, az un. gyökeret.
Gyökeres
d
-edfokú fa olyan gyökeres fa, melyben a
gyökér foka
d
és minden más pont foka
d
+
1
vagy
1
. Egy gyökeres
d
-edfokú fa teljes, ha minden végpontja a
gyökértől azonos távolságra van.
- Faktor
a
G
gráf
f
-faktora (ahol
f
egy
V
(
G
)
-n értelmezett függvény) olyan
G
′
részgráf, melyre
V
(
G
′
)
=
V
(
G
)
és
d
G
′
(
x
)
=
f
(
x
)
minden
x
pontra. Tehát az 1-faktor egy minden
pontot lefogó független élhalmaz.
- Félig reguláris csoport
lásd permutációcsoport.
- Felhasítás
a
G
gráf egy
x
pontjának felhasítása
x
1
,
…
,
x
k
pontokra az
x
elhagyásával,
x
1
,
…
,
x
k
új pontok felvételével és minden
(
x
,
y
)
-élnek (
y
∈
V
(
G
)
−
{
x
}
) pontosan egy
i
-re (
1
≤
i
≤
k
) egy új
(
x
i
,
y
)
-éllel való helyettesítésével előálló
gráf.
- Felosztás (
G
gráfé):
A
G
-ből oly módon előálló
G
′
gráf, hogy minden
e
élt egy
e
végpontjait összekötő és más
G
-beli pontot nem tartalmazó
P
e
(legalább 1 hosszú) úttal helyettesítünk
úgy, hogy a
P
e
utak (
e
∈
E
(
G
)
) függetlenek legyenek. A
G
pontjait a
G
′
főpontjainak nevezzük.
- Fenyő
egy irányított
G
gráf egy kitüntetett
a
ponttal, gyökérrel, melyben minden
x
≠
a
pont befoka 1 és minden
x
ponthoz vezet egy egyértelmű
(
a
,
x
)
-út. Fenyőt kaphatunk úgy, hogy egy
fában megjelölünk egy
a
pontot, majd minden
e
élt úgy irányítunk, hogy az
a
-t és
e
-t összekötő egyértelmű út
e
kezdőpontjában végződjön. Inverz fenyő
az az irányított gráf, melyet egy fenyőből az élek
irányításának megfordításával kapunk.
- Ferrers diagram
lásd
1.16.
- Feszített részgráf
lásd részgráf.
- Feszítő részgráf (
G
gráfé)
olyan
G
′
részgráf, melyre
V
(
G
′
)
=
V
(
G
)
.
- Fokszám
egy
x
pont foka egy
G
[hiper]gráfban az
x
-et tartalmazó élek száma (gráfok esetén
a hurokél kétszer számolandó).
x
fokszámát
d
G
(
x
)
jelöli.
d
(
G
)
a
G
-beli maximális fokszámot jelöli. Egy
gráf
k
-reguláris, ha minden pont foka
k
. Egy
x
pont befoka [kifoka] a
G
irányított gráfban azon élek számával
egyenlő, melyek végpontja [kezdőpontja]
x
-ben van; jelölése
d
G
−
(
x
)
[
d
G
+
(
x
)
].
- Folyam
Egy
(
a
,
b
)
-folyam az irányított
G
gráf élein értelmezett nemnegatív valós
f
függvény, melyre
minden
x
0
≠
a
,
b
pontra (vagyis az
x
0
-ba befolyó „víz” mennyisége azonos az
onnan kifolyó mennyiséggel; „Kirchhoff törvénye”). Egy
(
a
,
b
)
-folyam
f
értéke a „nettó nyereség” az
a
forrásnál, azaz
- Frucht tétele
lásd
12.5.
- Független élek egy [irányított] gráfban
semelyik kettőnek nincs közös végpontja. A
G
-beli független élek maximális számát
ν
(
G
)
jelöli. Egy független élhalmazt
párosításnak is nevezünk.
- Független pontok egy [irányított] gráfban
semelyik kettő között nem megy él. A
G
-beli független pontok maximális számát
α
(
G
)
jelöli.
- Független utak egy [irányított] gráfban
olyan utak, melyeknek nincsen közös pontjuk,
esetleg a végpontoktól eltekintve.
- Gallai–Edmonds struktúra tétel
lásd
7.32.
- Generátorfüggvény
egy
{
a
n
}
n
=
0
∞
sorozat generátorfüggvénye az
függvény. Exponenciális generátorfüggvény:
f
(
x
)
=
∑
n
=
0
∞
(
a
n
∕
n
!
)
x
n
.
- Geometriai háló
egy atomjai által generált
L
háló, melyben ha
x
fedi
x
∧
y
-t, akkor
x
∨
y
fedi
y
-t. Az
x
elem
r
(
x
)
rangja a
(
0
,
x
)
-sorozatok maximális hossza mínusz 1. Ez
a függvény eleget tesz a következőknek:
r
(
x
)
≥
0
;
x
>
x
′
⇒
r
(
x
)
≥
r
(
x
′
)
; ha
x
fedi
y
-t, akkor
r
(
y
)
≤
r
(
x
)
≤
r
(
y
)
+
1
; és
r
(
x
∨
y
)
+
r
(
x
∧
y
)
≤
r
(
x
)
+
r
(
y
)
. Ilyen hálóra példát szolgáltat egy
affin vagy projektív tér tetszőleges
S
ponthalmaza: a háló elemei a tér
altereinek
S
-sel vett metszetei.
- Gráf
a
G
gráf pontok (csúcsok) egy véges
V
(
G
)
halmazából és élek egy véges
E
(
G
)
halmazából, valamint egy
hozzárendelésből áll, mely minden
e
∈
E
(
G
)
élhez a
V
(
G
)
rendezetlen elem-párjait,
e
végpontjait rendeli. Jelölés:
G
=
(
V
(
G
)
,
E
(
G
)
)
. Azt mondjuk, hogy egy él összeköti,
vagy összekapcsolja a végpontjait. Ha
e
összeköti
x
-et és
y
-t, akkor
e
-t
(
x
,
y
)
-élnek nevezzük. Az olyan élt, melynek
két végpontja azonos, hurokélnek hívjuk. Két azonos
végpont-párral rendelkező él párhuzamos, vagy
többszörös.
A gráf egyszerű, ha nincs hurokéle, és nincsenek
párhuzamos élei. Ebben az esetben tekinthetjük
E
(
G
)
-t a
V
(
G
)
két elemű részhalmazainak halmazaként.
Egy él és egy pont szomszédos
(illeszkednek), ha a pont
az él egyik végpontja. Két él szomszédos, ha van közös
végpontjuk. Két pont szomszédos, ha él köti össze őket.
Egy ponthoz illeszkedő élek halmaza a pont csillaga. A
X
⊆
V
(
G
)
-vel szomszédos pontok halmazát
Γ
G
(
X
)
-szel, vagy egyszerűen
Γ
(
X
)
-szel jelöljük, ha a szóban forgó gráfot
a szövegkörnyezet egyértelművé teszi. A hurok nélküli
gráfok speciális hipergráfok (vö. még irányított
gráf).
- Hajós konstrukció
lásd
8.16.
- Háló
olyan részben rendezett halmaz, melyben bármely két
x
,
y
elemnek egyértelmű
x
∨
y
legkisebb felső korlátja (egyesítése) és
egyértelmű
x
∧
y
legnagyobb alsó korlátja (metszete) van.
Minden itt tárgyalt háló véges. Minden véges hálónak van
egy egyértelmű legkisebb eleme,
0
, és egyértelmű legnagyobb eleme,
1
. Egy legkisebb nem-nulla elemet atomnak
nevezünk.
- Hamilton kör [út]
egy [irányított] gráf minden pontját tartalmazó
[irányított] kör [út].
- Hamilton-féle gráf
van Hamilton-köre.
- Háromszögelés (
C
köré)
olyan gráf, mely ebből a körből
és ennek
n
−
3
nem kereszteződő átlójából áll (
n
a
C
hossza).
- Háromszögelt síkgráf
olyan síkgráf, melynek minden lapja
háromszög.
- Helyettesítés
a
H
gráf egy
x
pontjának a
G
gráffal való helyettesítését úgy kapjuk,
hogy az
x
pontot elhagyjuk
H
-ból, és minden
(
x
,
y
)
-él fejében (
y
∈
V
(
H
)
−
{
x
}
) behúzunk
∣
V
(
G
)
∣
számú
y
-t
G
pontjaival összekötő élt (feltesszük,
hogy
G
és
H
pont-diszjunktak).
- Híd
egy
G
1
részgráfhoz tartozó híd egy olyan
(összefüggő)
B
részgráf, hogy
B
vagy egyetlen él, melynek mindkét
végpontja
G
1
-beli, vagy a
G
−
V
(
G
1
)
egy összefüggő komponense azon
G
1
végpontú élekkel együtt, melyek ezt a
komponenst
G
1
-hez kötik.
G
1
hídjai particionálják
E
(
G
)
−
E
(
G
1
)
-et, azaz úgy is lehetne definiálni
őket, mint a következő ekvivalencia-reláció osztályai: „
e
1
=
e
2
vagy van
e
1
-et és
e
2
-t összekötő
G
1
-től diszjunkt út”.
- Hipergráf (halmaz-rendszer)
A
H
hipergráf pontok egy véges
V
(
H
)
halmazából, élek egy véges
E
(
G
)
halmazából és egy hozzárendelésből áll,
mely minden
E
élhez hozzárendeli
V
(
H
)
egy részhalmazát,
E
végpontjait (elemeit). Jelölése:
H
=
(
V
(
H
)
,
E
(
H
)
)
. Azonos végpontokkal rendelkező két él
párhuzamos. A hipergráf egyszerű,
ha nem tartalmaz párhuzamos éleket. Ebben az esetben
E
(
H
)
-t tekinthetjük úgy, mint
V
(
H
)
részhalmazainak egy halmazát. Egy él
illeszkedik egy ponthoz, ha a pont az él egyik végpontja.
A hipergráf
r
-uniform, ha minden élnek
r
végpontja van. A 2-uniform hipergráfokat
azonosíthatjuk a hurokmentes gráfokkal. Az
n
pontú teljes
r
-uniform hipergráf egy olyan egyszerű
hipergráf, mely a pontjainak minden
r
elemű részhalmazát tartalmazza élként.
Jelölése
K
n
r
.
- Homomorfizmus
egy
G
1
[irányított] gráf homomorfizmusa egy
G
2
[irányított] gráfba: egy olyan
ϕ
:
V
(
G
1
)
→
V
(
G
2
)
leképezés, hogy ha
(
x
,
y
)
∈
E
(
G
1
)
, akkor
(
ϕ
(
x
)
,
ϕ
(
y
)
)
∈
E
(
G
2
)
.
- Húr
egy
G
1
⊆
G
részgráf húrja egy
e
∈
E
(
G
)
−
E
(
G
1
)
él, mely
G
1
két pontját köti össze.
- Hurokél
lásd gráf.
- Illeszkedési mátrix (
G
gráfé)
A
B
G
=
(
b
i
j
)
i
=
1
n
j
=
1
m
mátrix, ahol
V
(
G
)
=
{
v
1
,
…
,
v
n
}
,
E
(
G
)
=
{
e
1
,
…
,
e
m
}
, és
b
i
j
=
1
, ha
v
i
és
e
j
illeszkednek, különben 0.
- Intervallumgráf
olyan egyszerű gráf, melynek pontjai egy egyenes
intervallumai, és két pontja akkor és csak akkor
szomszédos, ha a megfelelő intervallumok metszik
egymást.
- Irányítás
lásd irányított gráf.
- Irányított gráf
egy
V
(
G
)
ponthalmaz, egy
E
(
G
)
élhalmaz és rendezett pontpárok
hozzárendelése minden élhez; ezen rendezett pár első
eleme az él kezdőpontja, második
eleme az él végpontja.
Két élt párhuzamosnak nevezünk, ha kezdő- és végpontjuk
azonos. Az irányított gráf egyszerű, ha nem tartalmaz
párhuzamos éleket. Ebben az esetben
E
(
G
)
tekinthető
V
(
G
)
×
V
(
G
)
egy részhalmazának. Ha
G
gráf és minden éléhez tartozó egyik
pontot kinevezzük kezdőpontnak, a másikat pedig
végpontnak, akkor egy irányított gráfot kapunk, amit
G
egy irányításának nevezünk. Ha
e
=
(
x
,
y
)
∈
E
(
G
)
, a következő kifejezések bármelyikét
használhatjuk:
e
x
-ből
y
-ba mutat;
y
elérhető
x
-ből
e
-n;
e
elhagyja
x
-et és eléri
y
-t;
e
végpontja
y
és kezdőpontja
x
. Vö. gráf.
- Irányított kör
lásd kör.
- Izolált pont egy gráfban
olyan pont, mely nem illeszkedik élhez.
- Izomorfizmus a
G
1
és
G
2
gráfok között
V
(
G
1
)
-nek a
V
(
G
2
)
-re való kölcsönösen egyértelmű
ϕ
leképezése és az
E
(
G
1
)
-nek az
E
(
G
2
)
-re való kölcsönösen egyértelmű
ϕ
˜
leképezése, melyek során ha
x
végpontja [kezdőpontja]
e
-nek, akkor
ϕ
(
x
)
végpontja [kezdőpontja]
ϕ
˜
(
e
)
-nek. Ha
G
1
és
G
2
egyszerűek, akkor
ϕ
˜
nem játszik fontos szerepet és az
izomorfizmust úgy definiáljuk, mint a
V
(
G
1
)
és
V
(
G
2
)
közötti
ϕ
kölcsönösen egyértelmű megfeleltetést,
melyre
(
x
,
y
)
∈
E
(
G
1
)
⇔
(
ϕ
(
x
)
,
ϕ
(
y
)
∈
E
(
G
2
)
)
.
- Karakterisztikus polinom (
G
gráfé)
a
p
G
(
λ
)
=
det
(
λ
I
−
A
G
)
polinom, ahol
A
G
a
G
csúcsmátrixa. Ez nem függ a pontok
számozásától. A karakterisztikus polinom gyökeit, azaz
A
G
sajátértékeit a
G
gráf sajátértékeinek nevezzük.
- Kerék
olyan gráf, melyet egy kör minden pontjának egy új
ponttal (a kerék „középpontjával”) való összekötésével
kapunk.
- Kerület (
G
gráfé)
a legrövidebb kör hossza. A
kerület akkor és csak akkor 1, ha
G
-ben van hurokél, és akkor és csak akkor
2, ha
G
-ben van többszörös él.
- Kiegyensúlyozott kör hipergráfban
olyan
(
x
1
,
E
1
,
…
,
x
k
,
E
k
)
kör, melyre vagy
k
=
2
, vagy van egy
x
i
∈
E
j
illeszkedés, ahol
j
≠
i
,
i
−
1
és
(
i
,
j
)
≠
(
1
,
k
)
. Egy hipergráf kiegyensúlyozott, ha
minden páratlan hosszú köre kiegyensúlyozott, és teljesen
kiegyensúlyozott, ha minden köre kiegyensúlyozott.
- Kiterjedési ráta
lásd konduktancia.
- Klikk
egy gráf maximális (nem bővíthető) teljes
részgráfja.
- Kollekció
egy
S
halmaz, melynek minden eleméhez egy
pozitív egész multiplicitás is meg van adva. Bármely nem
S
-beli elem multiplicitását 0-nak
tekintjük.
- Komplementer (egyszerű
G
gráfé)
az az egyszerű
G
¯
gráf, melyre
Nyilvánvaló, hogy
(
G
¯
)
¯
=
G
.
(egyszerű irányított
G
gráfé): az az egyszerű irányított
G
¯
gráf, melyre
- Komponens
Egy
G
gráf komponense (vagy összefüggő
komponense) minden maximális (nem bővíthető) összefüggő
részgráfja.
G
bármely két összefüggő komponense
pont-diszjunkt, és minden pont (és él) pontosan egy
komponensbe tartozik. A komponensek számát
c
(
G
)
-vel jelöljük ;
c
1
(
G
)
jelöli a páratlan sok pontot tartalmazó
komponensek számát. Egy irányított gráf erős komponense
minden maximális (nem bővíthető) erősen összefüggő
részgráfja.
- Konduktancia (egy
G
gráfé)
Az
kifejezés minimuma minden nem-üres
S
⊂
V
halmazra, ahol
e
(
S
,
V
∖
S
)
az
S
és
V
∖
S
közti elemek számát jelöli. A
kiterjedési ráta a pontokra vonatkozó analóg fogalom: a
∣
Γ
(
S
)
∖
S
∣
∣
S
∣
kifejezés minimuma minden olyan nem-üres
S
⊂
V
halmazra, melyre
∣
S
∣
≤
∣
V
∣
∕
2
.
- König tétele
lásd
7.2.
- Kör egy gráfban
olyan
(
x
1
,
e
1
,
…
,
x
k
,
e
k
,
x
k
+
1
)
séta, melyben
x
1
,
…
,
x
k
különböző pontok,
e
1
,
…
,
e
k
különböző élek és
x
1
=
x
k
+
1
. Ha a gráf egyszerű, ezt a kört
(
x
1
,
…
,
x
k
)
-val jelöljük.
irányított gráfban
olyan részhalmaz, hogy ha az irányított gráf éleit
azonos végpontú irányítatlan élekre cseréljük, ez kört
alkot az így kapott irányítatlan gráfban. irányított kör:
olyan
(
x
1
,
e
1
,
…
,
e
k
,
x
k
+
1
)
séta, melyben
x
1
,
…
,
x
k
különbözőek és
x
k
+
1
=
x
1
.
hipergráfban
egy
(
x
1
,
E
1
,
…
,
x
k
,
E
k
)
sorozat, ahol
x
1
,
…
,
x
k
különböző pontok,
E
1
,
…
,
E
k
különböző élek és
x
i
∈
E
i
(
i
=
1
,
…
,
k
)
,
x
i
+
1
∈
E
i
(
i
=
1
,
…
,
k
−
1
)
,
x
1
∈
E
k
.
k
a kör hossza.
- Kritikus
egy
G
gráf (él-)kritikus egy
P
tulajdonságra vonatkozóan, vagy
kritikusan rendelkezik a
P
tulajdonsággal, ha
G
igen, de bármely él elhagyása után a
kapott gráf már nem rendelkezik a
P
tulajdonsággal. Pont-kritikus ezzel
analóg módon definiálható.
α
-kritikus:
α
(
G
−
{
e
}
)
>
α
(
G
)
minden
e
élre.
χ
-kritikus:
χ
(
G
−
{
e
}
)
<
χ
(
G
)
minden
e
élre.
τ
-kritikus:
τ
(
G
−
{
e
}
)
<
τ
(
G
)
minden
e
élre.
ν
-kritikus hipergráf:
ν
(
H
−
x
)
=
ν
(
H
)
minden
x
∈
V
(
G
)
-re (vö.
7.26feladattal az
elnevezés magyarázatához).
faktor-kritikus gráf:
G
-ben nincsen 1-faktor, de
G
−
x
-ben van 1-faktor minden
x
pontra.
Kromatikus index (
G
[hiper]gráfé): az a legkisebb
k
egész, melyre
G
élei
k
-színezhetők úgy, hogy szomszédos élek
színe különböző. Jelölése:
q
(
G
)
. Nyilvánvaló, hogy
q
(
G
)
=
χ
(
L
(
G
)
)
.
- Kromatikus szám (
G
[irányított] gráfé, hipergráfé)
az a
legkisebb
k
egész, melyre
G
„jól
k
-színezhető”
(lásd színezés). Ezt a számot
χ
(
G
)
-vel jelöljük. Nyilvánvaló, hogy
χ
(
G
)
>
0
, ha
G
nem üres;
χ
(
G
)
>
1
, ha
E
(
G
)
nem üres.
χ
(
G
)
=
∞
, ha
G
-ben van hurokél [vagy hipergráfra, ha
van 2-nél kevesebb végpontú éle].
- Kromatikus polinom
(
G
gráfé):
P
G
(
λ
)
a
G
(
λ
=
0
,
1
,
…
)
jó
λ
-színezéseinek száma. Ez (rögzített
G
esetén)
λ
polinomja, így a definíció
kiterjeszthető minden valós (vagy komplex)
λ
értékre. Jegyezzük meg, hogy a színek
jelölésében eltérő két színezés különbözőnek
számít.
- Kuratowski tétele
lásd
5.38.
- Lap
lásd síkgráf.
- Laplace mátrix
a
v
1
,
…
,
v
n
pontokon értelmezett
G
gráfra az
L
G
=
(
ℓ
i
j
)
i
,
j
=
1
n
mátrix, ahol
ℓ
i
j
a
(
v
i
,
v
j
)
-élek számának ellentettje, ha
i
≠
j
, és
ℓ
i
i
az
i
-edik pont fokszáma.
d
-reguláris gráfra
L
G
=
d
I
−
A
G
.
- Lefedési idő
lásd véletlen séta.
k
-lefogás (
G
[hiper]gráfban): pontok olyan
kollekciója, melyből minden él legalább
k
-t tartalmaz. A (pont-)lefogás azonos az
1-lefogással; a minimális méretű pont-lefogást
τ
(
G
)
jelöli. A
k
-lefogást tekinthetjük egy olyan
t
:
V
(
G
)
→
{
0
,
1
,
…
}
leképezésként is, melyben
∑
x
∈
E
t
(
x
)
≥
k
minden
E
élre.
- Lefogó élhalmaz ([hiper]gráfé)
olyan élhalmaz, mely minden pontot
tartalmaz.
- Legszűkebb keresztmetszet tétele
lásd
6.71.
- Mag
egy irányított gráf pontjainak olyan
S
független halmaza, melyre minden
x
∈
V
(
G
)
−
S
-hez létezik olyan
y
∈
S
, melyre
(
y
,
x
)
∈
E
(
G
)
.
- Maximális folyam–minimális vágás tétel
lásd
6.74.
- Megszorítás
egy
H
hipergráf
X
⊆
V
(
H
)
-ra vonatkozó megszorítása: a
H
X
hipergráf az
X
halmazon, melyre
E
(
H
X
)
az
E
∩
X
(
E
∈
E
(
H
)
)
halmazok kollekciója. Ha
X
=
V
(
H
)
−
Y
, akkor további jelöléseket vezetünk be:
H
X
=
H
∖
Y
és
H
X
=
H
−
y
, ha
Y
=
{
y
}
.
- Menger tétel
lásd
6.39.
- Menettérti idő
lásd véletlen séta.
- Merev gráf
nincs valódi endomorfizmusa.
- Minimális út–maximális potenciál tétel
lásd
6.72.
- Möbius függvény
lásd
2.22.
- Möbius megfordítási formula
lásd
2.26.
- Összefüggő gráf
olyan gráf, mely nem reprezentálható
G
1
∪
G
2
alakban, ahol
G
1
és
G
2
pont-diszjunkt, nem üres gráfok. Vagy
ezzel ekvivalens megfogalmazásban: a gráf bármely két
pontját út köti össze. Egy irányított
G
gráf gyengén összefüggő, ha nem
reprezentálható
G
1
∪
G
2
alakban, ahol
G
1
és
G
2
pont-diszjunkt nem üres irányított
gráfok; erősen összefüggő, ha bármely két pontot
(irányított) út köt össze. Egy
H
hipergráf összefüggő, ha nem
reprezentálható
H
1
∪
H
2
alakban, ahol
H
1
,
H
2
pont-diszjunkt, nem üres hipergráfok.
Vegyük észre, hogy ha
∅
∈
E
(
H
)
, akkor
H
nem összefüggő.
- Összefüggőség
Egy
G
gráf
k
-szorosan összefüggő
a
és
b
között, ha
k
-nál kevesebb
(
a
,
b
)
-től különböző pontot és/vagy élt
elhagyva, még mindig létezik
(
a
,
b
)
-út a(z) [irányított] gráfban (élek
elhagyása csak akkor szükséges, ha
a
és
b
szomszédosak). Egy [irányított]
G
gráf
k
-szorosan összefüggő, ha legalább
k
+
1
pontja van, és
k
-szorosan összefüggő bármely két pontja
között. Ekvivalens alakban:
∣
V
(
G
)
∣
≥
k
+
1
és
G
−
X
[erősen] összefüggő bármely
X
⊂
V
(
G
)
,
∣
X
∣
≤
k
−
1
halmazra. Irányítatlan gráfra ez még úgy
is mondható, hogy
∣
V
(
G
)
∣
≥
k
+
1
és
G
nem reprezentálható
G
1
∪
G
2
alakban, ahol
V
(
G
1
)
,
V
(
G
2
)
≠
V
(
G
)
és
∣
V
(
G
1
)
∩
V
(
G
2
)
∣
≤
k
−
1
. A teljes
K
n
gráf így
(
n
−
1
)
-szeresen összefüggő, de nem
n
-szeresen összefüggő. Összefüggő és
1-összefüggő ekvivalens a legalább két pontú
gráfokra.
- Összehúzás
egy
e
él összehúzása egy [irányított] gráfban
az él elhagyását és a két végpontja azonosítását jelenti.
Egy részgráf összehúzása minden élének összehúzását
jelenti (az élek összehúzásának sorrendje nem számít).
Vegyük észre, hogy összehúzással keletkezhetnek
többszörös élek.
- Párhuzamos élek
lásd gráf,
irányított gráf,
hipergráf.
- Páros (2-kromatikus) gráf
Olyan
G
gráf, mely pontjain létezik egy
{
A
,
B
}
partíció, vagy 2-színezés, hogy minden
él egy
A
-beli és egy
B
-beli pontot köt össze (vö. kromatikus
szám).
- Párosítás
egy
k
-párosítás a
G
[hiper]gráfban a
G
éleinek egy olyan részhalmaza, melyből
minden ponthoz legfeljebb
k
illeszkedik (az élek ismétlése meg van
engedve). Az 1-párosításokat egyszerűen párosításnak
nevezzük. A
G
-beli legnagyobb párosítás elemszáma
ν
(
G
)
; legyen
ν
(
G
)
=
∞
, ha
∅
∈
G
. A
k
-párosítást tekinthetjük egy olyan
w
:
E
(
G
)
→
{
0
,
1
,
…
}
leképezésnek, melyre
∑
E
∋
x
w
(
E
)
≤
k
minden
x
pontra (
w
(
E
)
az
E
multiplicitása a párosításban). A teljes
k
-párosítás olyan
k
-párosítás, melynek minden pont pontosan
k
eleméhez tartozik (vegyük észre a
különbséget ez és egy
k
-faktor között: ott a
G
egy éle legfeljebb egyszer szerepelhet).
Törtpárosítás: olyan nem-negatív valós
w
(
e
)
súlyok hozzárendelése minden
e
élhez, melyre
∑
E
∋
x
w
(
e
)
≤
1
minden
x
pontra. A törtpárosítás
w
mérete a
∑
e
∈
E
(
G
)
w
(
e
)
érték; a törtpárosítás minimális méretét
ν
∗
(
G
)
jelöli.
- Partíció (
S
halmazé)
S
nem-üres diszjunkt részhalmazinak
{
A
1
,
…
,
A
k
}
rendszere (ezek a partíció osztályai),
melyre
A
1
,
∪
…
∪
A
k
=
S
. Egy
n
-elemű halmaz partícióinak
B
n
számát Bell számnak hívjuk.
(
n
számé): pozitív egészek egy
{
a
,
…
,
a
k
}
(
a
1
≥
…
≥
a
k
) kollekciója, melyre
a
1
+
…
+
a
k
=
n
.
- Perfekt gráf
olyan egyszerű
G
gráf, melynek minden feszített
G
′
részgráfjára
- Permanens (egy
(
a
i
j
)
i
=
1
n
j
=
1
n
mátrixé)
ahol
π
végigfut
{
1
,
…
,
n
}
összes permutációján.
- Permutáció (egy
Ω
halmazé)
Ω
egy saját magára történő kölcsönösen
egyértelmű leképezése. Egy
n
-elemű halmaz permutációinak száma
n
!
=
1
⋅
2
⋅
…
⋅
n
. A minden elemet helybenhagyó
permutációt 1 jelöli. Ha
γ
az
Ω
egy permutációja,
x
∈
Ω
, és
γ
(
x
)
=
x
, akkor
x
a
γ
egy fixpontja.
- Permutációcsoport
olyan
Γ
csoport, melynek minden
γ
eleméhez hozzá van rendelve egy véges
Ω
halmaz egy
γ
˜
∈
Γ
permutációja úgy, hogy
γ
δ
(
x
)
˜
=
δ
˜
(
γ
˜
(
x
)
)
(
γ
,
δ
∈
Γ
). Ha ebből félreértés nem származhat,
fel fogjuk tenni, hogy
Γ
elemei maguk is permutációk, és esetleg
ismétlődhetnek is. Ha
γ
˜
=
δ
˜
-ból
γ
=
δ
következik, vagy ezzel ekvivalensen
γ
≠
1
-re
γ
˜
≠
1
, akkor a permutációcsoport effektív. Ha
bármely
x
,
y
∈
Ω
párhoz legfeljebb egy olyan
γ
∈
Γ
létezik, melyre
γ
(
x
)
=
y
, akkor a csoport tranzitív. Ha bármely
x
,
y
∈
Ω
párhoz legfeljebb egy
γ
∈
Γ
létezik, melyre
γ
(
x
)
=
y
, vagy (ekvivalens alakban) egyetlen
γ
∈
Γ
,
γ
≠
1
-ben sincsen fixpont, akkor a
permutációcsoport félig reguláris. Ha félig reguláris és
tranzitív is egyben, akkor regulárisnak nevezzük. Ebben
az esetben
∣
Γ
∣
=
∣
Ω
∣
és
Ω
elemei azonosíthatók
Γ
elemeivel úgy, hogy
γ
(
δ
)
=
δ
γ
minden
γ
,
δ
∈
Γ
-ra.
- Petersen gráf
lásd
9. ábra.
- Pfaffian (ferdén szimmetrikus mátrixé)
Ha
A
=
(
a
i
j
)
i
=
1
2
n
j
=
1
2
n
ferdén szimmetrikus (azaz
a
i
i
=
0
,
a
i
j
=
−
a
j
i
), akkor
ahol
ɛ
i
1
j
1
,
…
,
i
n
j
n
a
permutáció előjele, és a szummázás
{
1
,
…
,
2
n
}
minden
{
{
i
1
,
j
1
}
,
…
,
{
i
n
,
j
n
}
}
alakú partíciójára megy. Könnyen
látható, hogy az
{
{
i
1
,
j
1
}
,
…
,
{
i
n
,
j
n
}
}
partícióhoz tartozó tag nem függ az
osztályok sorrendjétől és egy osztályon belüli két elem
sorrendjétől sem.
- Pont
lásd gráf,
irányított gráf,
hipergráf.
- Pólya leszámlálási módszere
lásd
3.26–30.
- Prüfer kód
lásd
4.5.
- Pszeudoszimmetrikus irányított gráf
lásd szimmetrikus.
- Ramsey tétel
lásd 14. fejezet.
- Reguláris gráf
lásd fokszám;
- Reguláris csoport
lásd permutációcsoport.
- Reprezentáns-rendszer (
H
hipergráfé)
olyan injektív
ϱ
:
E
(
H
)
→
V
(
H
)
leképezés, melyre
ϱ
(
E
)
∈
E
minden
E
∈
E
(
H
)
-ra. Ha nem adódhat félreértés, szokás a
ϱ
(
E
(
H
)
)
értékkészletet is
reprezentáns-rendszernek nevezni.
- Részgráf (
G
gráfé)
olyan
G
′
gráf, melyre
V
(
G
′
)
⊆
V
(
G
)
és
E
(
G
′
)
⊆
E
(
G
)
. Jelölése:
G
′
⊆
G
. A
G
egy
X
⊆
V
(
G
)
halmaza által feszített részgráfja az a
G
[
X
]
gráf, melyre
V
(
G
[
X
]
)
=
X
,
E
(
G
[
X
]
)
=
{
e
∈
E
(
G
)
:
e
⊆
X
}
.
- Rész-hipergráf (
H
hipergráfé)
olyan
H
′
hipergráf, melyre
V
(
H
′
)
⊆
V
(
H
)
,
E
(
H
′
)
⊆
E
(
H
)
.
- Selberg szita
lásd
2.14–17.
- Séta egy [irányított] gráfban
olyan
(
x
1
,
e
x
,
…
,
x
k
,
e
k
,
x
k
+
1
)
sorozat, melyre
x
1
,
…
,
x
k
a gráf pontjai és
e
i
egy
(
x
i
,
x
i
+
1
)
-él (
i
=
1
,
…
,
k
). Ha a(z) [irányított] gráf egyszerű, a
sétát leírhatjuk az
(
x
1
,
…
,
x
k
+
1
)
sorozattal is. A séta akkor és csak
akkor nyílt [zárt], ha
x
k
+
1
≠
x
1
[
x
k
+
1
=
x
1
]. A séta hossza a fenti
k
. A séta egy vonal, ha egy élt sem
használunk egynél többször.
- Síkgráf
olyan gráf, melynek pontjai a sík pontjai, és élei
(a végpontnak megfelelő síkbeli pontban végződő) síkbeli
Jordan görbék, melyeknek a végpontokon kívül nincsen
közös pontjuk. A halmaz egy összefüggő komponensét,
melyet egy síkgráf éleinek és pontjainak a síkból való
elhagyásával kapunk, lapnak
(országnak) nevezünk. Egy lap
határa mindig bizonyos élek uniója; ha a
G
síkgráf 2-összefüggő gráf, akkor minden
lap határa a
G
egy körének éleiből álló zárt
Jordan-görbe. Ha egy (absztrakt)
G
gráf izomorf egy
G
0
síkgráffal, akkor síkbarajzolhatónak
hívjuk. A
G
0
síkgráfot a
G
egy síkba való beágyazásának
nevezünk.
- Szita formula
lásd 2. fejezet.
- Szorzat
két egyszerű [irányított]
G
1
és
G
2
gráf szorzatát háromféleképpen
értelmezzük:
(Gyenge) direkt szorzat
G
1
×
G
2
:
Erős direkt szorzat
G
1
⋅
G
2
:
Descartes szorzat
G
1
⊕
G
2
:
Tehát
G
1
⋅
G
2
=
(
G
1
×
G
2
)
∪
(
G
1
⊕
G
2
)
(lásd
121. ábra).
két hipergráf,
H
1
,
H
2
direkt szorzata: a következők szerint
definiált
H
1
×
H
2
hipergráf:
- Spektrum
egy
G
gráf spektruma a
G
A
G
szomszédossági mátrixának spektruma
(sajátértékeinek összessége). Mivel
A
G
szimmetrikus,
G
sajátértékei (a spektruma elemei)
valósak.
- Sperner lemma
lásd
5.29.
- Sperner tétel
lásd
13.21.
- Sperner-rendszer
olyan hipergráf, melyben egyetlen él sem tartalmaz
másik élt.
- Stacionárius eloszlás
(egy gráfon tett véletlen sétáé): lásd
11.35.
Stirling ciklusszám
n
k
: egy
n
-elemű, pontosan
k
ciklusú halmaz permutációinak száma. A
(
−
1
)
n
−
k
n
k
számokat szokás elsőfajú Stirling
számoknak nevezni, és
s
(
n
,
k
)
-val jelölni.
- Stirling partíciószám
n
k
:
n
dolog pontosan
k
osztályba particionálásainak száma.
Ezeket a számokat szokás másodfajú Stirling számoknak
nevezni, és
S
(
n
,
k
)
-val jelölni.
- Szimmetrikus irányított gráf
olyan egyszerű irányított gráf, melyben minden
(
x
,
y
)
∈
E
(
G
)
élhez van egy
(
y
,
x
)
∈
E
(
G
)
él. Pszeudoszimmetrikus:
d
+
(
x
)
=
d
−
(
x
)
minden pontban.
- Színezés
egy gráf [irányított gráf, hipergráf] (érvényes,
jó)
k
-színezése „színek” (általában az
1
,
…
,
k
egészek) hozzárendelése a pontokhoz oly
módon, hogy minden él végpontjai különböző
„színűek”.
-
k
-színezhető,
k
színnel színezhető gráf [irányított
gráf, hipergráf]
van jó
k
-színezése.
- Szomszédos
lásd gráf.
- Tag egy
G
gráfban
elvágóél vagy maximális
2-összefüggő részgráf. Minden élt egyetlen tag tartalmaz.
A tagokat definiálhatjuk az
E
(
G
)
-n értelmezett „
e
és
f
egy körön van vagy
e
=
f
” ekvivalencia-reláció osztályaiként is.
Egy gráf tagjai „kaktusz-szerű” struktúrát adnak; minden
egynél több tagba tartozó pont elvágópont, és bármely
ponthoz tartozó ágak száma egyenlő a pontot tartalmazó
tagok számával (122. ábra). Az egyetlen
elvágópontot tartalmazó tagokat végtagnak hívjuk.
- Távolság
a
G
gráfbeli
x
és
y
pontok közti távolság az
(
x
,
y
)
-utak minimális hossza; ha nincsen
G
-ben
x
-et és
y
-t összekötő út, a távolságuk
∞
. Jelölése
d
G
(
x
,
y
)
, vagy röviden
d
(
x
,
y
)
, ha egyértelmű, hogy melyik gráfról van
szó.
- Teljes gráf
egyszerű gráf, melyben bármely két különböző pont
szomszédos. Az
n
pontú teljes gráfot
K
n
jelöli.
Teljes gyökeres
d
-edrendű fa: lásd fa.
- Teljes páros gráf
olyan egyszerű gráf, melynek pontjai két
U
,
W
osztályba sorolhatók úgy, hogy két pont
akkor és csak akkor szomszédos, ha egyik
U
-beli, a másik
W
-beli. Ha
∣
U
∣
=
n
és
∣
W
∣
=
m
, akkor a teljes páros gráfot
K
n
,
m
jelöli.
- Törtlefogás a
G
[hiper]gráfban
egy nem-negatív valós
t
(
x
)
súly hozzárendelése minden
x
ponthoz úgy, hogy
∑
x
∈
E
t
(
x
)
≥
1
minden
E
élre. A törtlefogás mérete
∑
x
∈
V
(
G
)
t
(
x
)
. A minimális méretű törtlefogást
τ
∗
(
G
)
jelöli.
- Tranzitív turnament
olyan
T
turnament, melyben
(
x
,
y
)
∈
E
(
T
)
és
(
y
,
z
)
∈
E
(
T
)
-ból
(
x
,
y
)
∈
E
(
T
)
következik. Egy tranzitív turnament
pontjai olyan
(
x
1
,
…
,
x
n
)
sorrendbe rendezhetők, hogy
(
x
i
,
x
j
)
∈
E
(
G
)
↔
i
<
j
.
- Tranzitív permutációcsoport
lásd permutációcsoport.
- Turán tétel
lásd
10.34.
- Turnament
olyan (egyszerű) irányított hurokmentes
T
gráf, melynek minden
x
≠
y
,
x
,
y
∈
V
(
T
)
párra
(
x
,
y
)
és
(
y
,
x
)
közül pontosan az egyik éle.
- Tutte tétele
lásd
7.27.
- Uniform
lásd hipergráf.
- Út egy [irányított] gráfban
Egy
(
x
1
,
e
1
,
…
,
e
k
,
x
k
+
1
)
séta, ahol
x
1
,
…
,
x
k
+
1
különböző pontok. Jelölhetjük
(
x
1
,
…
,
x
k
+
1
)
-gyel, ha a(z) [irányított] gráf
egyszerű.
-
(
X
,
Y
)
-út
olyan út a(z) [irányított] gráfban,
mely az
X
egy pontját az
Y
egy pontjával köti össze, és nincsen más
közös pontja
X
∪
Y
-nal.
- Üres [hiper]gráf
nincsen se éle, se pontja.
- Vágás
(
a
,
b
)
-vágás az olyan
F
élhalmaz, mely minden
(
a
,
b
)
-utat reprezentál (lefog). Az
S
⊆
V
(
G
)
által meghatározott vágás az
S
-t
V
(
G
)
−
S
-hez kapcsoló élek halmaza. Ha
C
az
S
′
által meghatározott vágás a
G
irányított gráfban, akkor
C
∗
a
V
(
G
)
−
S
által meghatározott vágás.
- Végpont (
G
gráfé)
elsőfokú pont.
Él végpontja: lásd gráf.
- Véletlen séta egy
G
gráfon
a
v
0
,
v
1
,
v
2
,
…
véletlen pontok (végtelen) sorozata,
ahol
v
0
-t valamely adott (gyakran egyetlen
pontra koncentrált) kezdeti eloszlásból választjuk, és
minden
i
≥
0
-ra
v
i
+
1
-et a
v
i
szomszédain vett egyenletes eloszlásból
választjuk. Az
u
pontból a
v
pont elérési ideje az
u
pontból induló véletlen séta várható
lépésszáma
v
érintéséig; jelölése:
H
(
u
,
v
)
. Az
u
és
v
élek közötti menettérti idő az
u
pontból a
v
és a
v
pontból az
u
elérési idejének összege; jelölése:
κ
(
u
,
v
)
. Az
u
pont lefedési ideje az
u
pontból induló véletlen séta várható
lépésszáma addig, míg az összes pontot érinti. Egy gráf
elérési [lefedési] ideje a maximális elérési [lefedési]
idő minden
u
,
v
-re .
- Vonal
lásd séta.
-
Θ
-gráf
olyan gráf, mely két pontot
összekötő három független útból áll.