grafe/o

1.

[grafe.0o.strukturo]

[1] Tia matematika strukturo `(bb E,U)`, ke `bb E` estas aro (aro de la verticoj) kaj `U` estas vico, kies termoj estas duopoj el elementoj en `bb E` (vico de ĝiaj eĝoj): grafeo estas prezentebla per aro da punktoj (la verticoj), ligitaj per linioj aŭ sagoj (la eĝoj); ebena grafeo (desegnebla sur ebeno sen interkruciĝoj). grafo; Atributoj: vertico, eĝo, buklo, ordo; Specifaj grafeoj: orientita grafeo, neorientita grafeo, simpla grafeo, n-grafeo, plurgrafeo, arbo; sub- kaj super-strukturoj: subgrafeo, supergrafeo. Specifaj partoj de grafeo: kliko, koneksa komponanto; Specifaj ecoj de grafeo: n-opeĝa, senbukla, eŭlera, kompleta, koneksa, koneksega, sencikla; Koneksaj nocioj: ĉeno, ciklo, vojo, cirkvito.

Rim.: Oni ankaŭ trovas la vorton „grafo“ uzatan tiusence, ekz-e en MatVort kaj PIV2. Nemulte gravas ĝia koincido kun la nobeltitolo, pli malbonas, ke ĝi povas kolizii kun la kvazaŭsufikso „-graf“. Ĉar ankoraŭ ne ekzistas firma tradicio en la kampo, kaj ĉar „grafeo“ jam aperis en pluraj verkoj, ni favoras tiun iom pli oportunan terminon.

Rim.: Ekzistas pluraj ekvivalentaj difinoj, provantaj pli-malpli bone ampleksi la diversajn tipojn de grafeoj: orientitaj aŭ ne, unuopeĝaj aŭ pluropeĝaj ktp. Ni elektis difinon, kiu favoras la nocion de pluropeĝa orientita grafeo. Notu, ke en pluropeĝa grafeo oni nomas eĝo ne nur la duopon el verticoj, sed foje ankaŭ tian duopon, konsideratan kune kun ĝia indico en la vico `U`. Tiamaniere eblas pravigi esprimojn de la tipo paralelaj eĝoj (eĝoj kun samaj randoj) aŭ du eĝoj ligas verticojn `v_1` kaj `v_2`.

2.

[grafe.0o.rilato]

(de rilato ^4.b) Diagramo, foje uzata por ĝin prezenti, konsistanta el sagoj, kies randoj prezentas tiajn elementojn `a` kaj `b`, ke `(a,b)` estas elemento de la rilato: en la grafeo de simetria rilato, al ĉiu sago respondas sago kun samaj randoj kaj kontraŭa direkto.

Rim.: Mi neniam vidis tian prezenton de rilatoj (krom eble la genealogiajn arbojn, kiuj tamen prezentas plurajn rilatojn samtempe); sed mi plurfoje vidis la uzojn de nacilingva „graphe d'une relation“ kiam fakte temis pri grafikaĵo de rilato (ekz-e la aro de karteziaj duopoj, obeantaj la rilaton `x^2+y^2=1`, vd rimarkon). En la tekstoj matematikaj normale temas pri la arteoriaj „grafikaĵoj de rilato“, kaj tiusenca misuzo de grafeo estas (laŭ mi) eraro kiun kaŭzas nacilingva homonimio. [Sergio Pokrovskij]

[2]

n-opeĝa grafeo.

^KompLeks

n-Grafeo kun `n gt 1`.

^KompLeks

(de grafeo `(bb E,U)`) Tia grafeo `(bb F,V)`, ke `bb F` estas subaro de `bb E` kaj `V` estas subvico de `U`: la subgrafeo naskita de subaro de verticoj (tia, ke `V` enhavas ĉiujn termojn de `U`, kies randoj apartenas al la koncerna subaro).

(de grafeo `(bb E,U)`) Tia grafeo, ke `(bb E,U)` estas subgrafeo de ĝi.

[3]

grafeiko

[4]

grafeo.

Rim. 1: Kongrue kun la nacilingva ĥaoso eblus uzi ankaŭ la adjektivon „direktita“ anstataŭ „orientita“, kiel aperas en [5], aŭ eĉ „digrafo“ (samloke).

Rim. 2: Kvankam en multaj nacilingvoj oni konfuzas orientitajn grafeojn kun la direktaj (kiel konstatas la ĉi-supra rimarko anonima), en la flegita uzado tiuj terminoj indikas malsamajn nociojn. La „direkta grafeo“ temas pri eĝoj dise, ke la eĝoj havas direkton, sen atenti pri ilia kuna kohero (kaj fuŝa estas la uzo de participo: ne la grafeon oni direktas sed la eĝojn). La „orientita grafeo“ temas pri ia kohero de la direktoj; interalie, orientita grafeo estas normale unugrafeo; kaj la eĝoj formas vojojn ‐ ekz-e oni distingas „alradike orientitan arbon“ (la idoj almontras sian patron) kaj „elradike orientitan arbon“ (la patroj almontras siajn idojn). Tio harmonias kun la geometria uzo de orientiĝo², kiu simile temas pri la aranĝo de la tuta strukturo (spaco, bazo). [Sergio Pokrovskij]

[6]

Grafeo, por kiu oni konvencie identigas la inversajn eĝojn `(x,y)` kaj `(y,x)`; alidire: la eĝoj de neorientita grafeo ne estas duopoj, sed du- aŭ unu-elementaj subaroj de la aro de verticoj.

Rim.: Al neorientita grafeo ĉiam eblas asocii orientitan. Sufiĉas konsideri, ke la eĝo `{x,y}` respondas al la du eĝoj `(x,y)` kaj `(y,x)`, kaj ke la buklo `{x}` respondas al `(x,x)`. Danke al tiu konvencio, ĉio, kio validas por orientita grafeo ricevas signifon ankaŭ por neorientita.

^MatVort

Neorientita grafeo, kiu estas unuopeĝa kaj senbukla.