Antaŭan paĝon! Indekson! Instrukcion!

El grafeiko

  1. Formala difino de grafeo
  2. Aplikoj de grafeoj
  3. Ekstera prezento de grafeoj
  4. Interna prezento de grafeoj
  5. Arboj
  6. La Konigsbergaj pontoj: problemo de Eŭlero

Formala difino de grafeo

Formale, grafeo estas triopo (V,E,P) el du disaj aroj — nevakua V (la verticoj) kaj E (la eĝoj) — kaj triloka predikato P super V×E×V indikanta, ĉu du verticojn el V ligas koncerna eĝo el E; eĝo ligas ne pli ol du verticojn.

Estu u, v∈V kaj e∈E; se veras P(u,e,v), tiam la verticoj u kaj v estas najbaraj; la eĝo e estas incida al v (iras al v) kaj u (iras el u); tial la predikaton P oni nomas incidpredikato. Ĉiu eĝo e apartenas al unu el la tri specoj:

Simetria eĝo
(∃x,y∈V)[x≠y ∧ P(x,e,y) ∧ P(y,e,x)].
Direkta eĝo
(∃x,y∈V)[x≠y ∧ P(x,e,y) ∧ ¬P(y,e,x)]; iuj aŭtoroj nomas tian eĝon arko.
Maŝo
(∃x∈V)P(x,e,x).

Aplikoj de grafeoj

La nocio «grafeo» utilas kiam temas pri du aroj da objektoj, kaj la elementoj de la dua aro rolas kiel ligiloj, popare rilatigantaj la anojn de la unua. Ekz-e elementoj de cirkvito kaj konektoj inter ili; la urboj kaj la trajnoj (la fervoja reto); la homoj kaj la rilatoj inter ili (amika, parenca ktp); strukturaj formuloj ĥemiaj. Por unu sama duopo oni povas konsideri plurajn tiajn rilatojn, kiuj povas esti simetriaj aŭ unudirektaj; ne maleblas rilato de objekto kun si mem. Plej ofte temas pri grafeo kies ĉiuj eĝoj estas direktaj (direkta grafeo) aŭ ĉiuj eĝoj estas simetriaj (sendirekta grafeo); ekzemplo pri miksa («nedirekta» aŭ «parte direkta») grafeo estas urba trafikmapo, montranta unusencumajn kaj dusencumajn stratojn (direktajn kaj simetriajn eĝojn).

Ekstera prezento de grafeoj

Grafeon oni ofte bildigas per desegno, ekz-e

[Desegno]

La grafeo

[Kuba grafeo]
klarigas la ideon motivantan la terminojn «vertico» kaj «eĝo»; verdire, la pluredroj estas tre speciala okazo de grafeoj. Fakte la nocio «grafeo» ne estas apartenaĵo de la «kontinua matematiko»; la formala difino uzas nur tre ĝeneralajn nociojn de la arteorio (kp grafikaĵo), kaj krom la geometriajn oni ankaŭ uzas tute diskretajn prezentojn — ekz-e per incidmatrico. En tiu prezento la rilaton inter vertico vi kaj eĝo ej esprimas la elemento de matrico M[i,j] laŭ unu el la sekvaj okazoj:

0
vi kaj ej ne estas incidaj;
A
ej estas direkta eĝo alvenanta en vi;
D
ej estas direkta eĝo deiranta el vi;
M
ej estas maŝo incida al vi;
S
ej estas simetria eĝo incida al vi.
Tiel la supre desegnitan grafeon prezentas la sekva incidmatrico M:

  1 2 3 4 5 6 7
u M M M D 0 0 D
v 0 0 0 A D S 0
w 0 0 0 0 A S A

Estu R libera duonringo kun la generantaro

{0,A,D,M,S}

kaj MTestu la transponaĵo de M. Tiam la kvadrata matrico B=M⋅MT super R estas la vertica najbarmatrico, dum H=MT⋅M estas la eĝa najbarmatrico. Tiu dua estas uzata multe pli malofte ol la unua, tial per senadjektiva «najbarmatrico» oni kutime nomas la vertican najbarmatricon.

En la praktiko grafeoj ofte estas prezentataj per listojligillistoj (Interna prezento de grafeoj); ankaŭ vd duuma arbo.

La dirita ne signifas, ke la grafea problemaro ne estas rilatigebla al geometrio; ekz-e, oni povus konsideri problemon tre interesan por la praktiko: ĉu donita grafeo desegneblas tiel, ke la linipecoj prezentantaj diversajn eĝojn ne interkruciĝas — t.e. ĉu la grafeo estas ebena grafeo; ekz-e la grafeo [vd] estas ebena, dum

[Neebena grafeo] estas neebena.

Grafeo estas n-obleĝa, aŭ n-grafeo, se neniajn du ĝiajn verticojn ligas pli ol n eĝoj, t.e. por ĉiuj u,v∈V veras

|{e∈E: P(u,e,v)∨P(v,e,u)}| ≤ n. 

Por la direktaj grafeoj oni nombras nur la samdirektajn eĝojn:

|{e∈E: P(u,e,v)}| ≤ n. 

Speciale menciindas nulgrafeo (aŭ 0-grafeo, vakua grafeo), unugrafeo kaj plurgrafeo (n-grafeo kiu ne estas 1-grafeo, n>1; ekz-e [vd]). Kutime oni identigas izomorfajn grafeojn.

Rim. Iuj aŭtoroj simpligas la difinon de grafeo, reduktante grafeon al duloka rilato (t.e. difinas eĝon kiel verticduopon); tio malebligas la plurgrafeojn, kiuj ja estas uzataj por priskribi aŭtomatojn, gramatikojn (vd sintaksa diagramo) ktp; la problemo pri la Konigsbergaj pontoj, de kiu komenciĝis grafeiko, kondukas al 2-grafeo (vd La Konigsbergaj pontoj). Kp arbo, hamako, kompleta grafeo, koneksa grafeo, reto, subgrafeo, supergrafeo, vojo. Sekvan paĝon Indekson Instrukcion