Točka (teorija grafov)

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Tóčka (vozlíšče ali vôzel) je v teoriji grafov osnovna enota, iz katere so sestavljeni grafi. Neusmerjene grafe sestavljata množica točk in množica povezav (neurejene pare točk), usmerjene grafe pa sestavljata množica točk in množica lokov (urejenih parov točk). Iz zornega kota teorije grafov se točke obravnavajo kot brezoblični in nedeljivi objekti, čeprav imajo lahko dodatno zgradbo, kar je odvisno od uporabe v kateri se pojavlja graf. Semantična mreža je na primer graf v katerem točke predstavljajo koncepte ali razrede objektov.

Izolirana točka predstavlja tudi polni graf K_{1} (prazni graf N_{1})

Dve točki, ki tvorita povezavo, sta njeni končni točki, povezava pa vodi v njiju - je incidenčna z njima. Točka w je sosedna drugi točki v, če graf vsebuje povezavo (v,w). Okolica točke v je inducirani podgraf grafa, nastal na vseh točkah, sosednih točki v.

Stopnja točke v grafu je število povezav incidenčnih z njo. Izolirana točka je točka s stopnjo 0, in ni končna točka nobene povezave. Hkrati predstavlja polni graf K_{1}, ki se imenuje prazni graf N_{1}. List (tudi pendantna točka) je točka s stopnjo 1.

V usmerjenem grafu ločimo med izhodno stopnjo (število odhajajočih povezav) in vhodno stopnjo (število prihajajočih povezav). Izvirna točka je točka z izhodno stopnjo 0, ponirna točka pa je točka z vhodno stopnjo 0.

Točke v grafih ustrezajo ogliščem poliedrov, vendar jim niso enake. Skelet poliedra tvori graf, katerega točke so njegova oglišča, poliedrska oglišča pa imajo dodatno značilnost (svojo geometrijsko lego), ki se v grafih ne pojavlja. Ogliščna figura oglišča v poliedru predstavlja okolico točke v grafu.

Viri[uredi | uredi kodo]

  • Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Pariz 1958, viii+277 pp. (angleška izdaja, Wiley 1961; Methuen & Co, New York 1962; ruska izdaja, Moskva 1961; španska izdaja, Mehika 1962; romunska izdaja, Bukarešta 1969; kitajska izdaja, Šanghaj 1963; druga izdaja prve angleške izdaje iz 1962. Dover, New York 2001)
  • Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9. 
  • Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. New York: Academic Press. ISBN 0-12-324245-2. 

Zunanje povezave[uredi | uredi kodo]