La artikolo estas parto de serio pri grafeoteorio.
|
Plej gravaj terminoj Elektitaj klasoj de grafeoj pli...
Grafeaj algoritmoj Problemoj prezentataj kiel grafeaj Aliaj Reprezentado de grafeo Glosaro de grafeoteorio |
En matematiko kaj komputiko, grafeo estas (neformale) aro da objektoj nomataj verticoj kunigitaj de ligoj nomataj eĝoj aŭ lateroj. Kutime, grafeo estas prezentata kiel aro da punktoj (la verticoj) ligitaj per linioj (la eĝoj). Depende de la apliko, iuj eĝoj povas esti direktitaj.
Grafeo estas baza objekto en grafeoteorio.
Difinoj de grafeo en grafeoteorio varias en la literaturo. Jen estas unu el la konvencioj.
Nedirektita grafeo aŭ grafeo G estas ordigita duopo G := (V, E):
V (kaj de ĉi tie E) kutime estas finia aro, kaj multaj el la konataj rezultoj ne estas veraj (aŭ estas iom malsamaj) por nefinia grafeoj, ĉar multaj el la argumentoj ne validas en la nefinia kazo.
Orientita grafeo aŭ G estas ordigita duopo G:=(V, A) kun
Miksita grafeo G estas ordita triopo G := (V,E,A) kie V, E kaj A estas difinitaj kiel pli supre.
Du eĝoj de grafeo) estas nomataj najbaraj, se ili havas komunan verticon. Simile, du verticoj estas nomataj najbaraj se ili havas komunan eĝon, do ili estas kunigitaj per eĝo. Vertico kaj eĝo, kiu ligas ĝin al alia vertico, estas nomataj incidaj.