Teorija grafikona

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Crtanje grafikona.

U matematici i računarstvu, teorija grafikona jeste proučavanje grafikona, koji su matematičke strukture korištene za modeliranje parova odnosa između objekata. Grafikon u ovom kontektstu je napravljen od tjemena, čvorova, ili tačaka koje se spajaju ivicama, lukovima ili linijama. Grafikon može biti neusmjeren, što znači da nema razlike između dva tjemena povezana s ivicom, ili njeni vrhovi mogu biti usmjereni sa jednog tjemena na drugo. Grafikoni su jedni od primarnih predmeta studija u diskretnoj matematici.

Definicije[uredi | uredi izvor]

Definicije u teoriji grafikona variraju. Ovdje su samo neke od osnovnih načina definiranja grafikona i povezanih matematičkih struktura.

Grafikon[uredi | uredi izvor]

U općenitom smislu pojma,[1][2] grafikon je poredani par G = (V, E) koji se sastoji od skupa V tjemena ili čvorova ili tačaka zajedno sa skupom E ivica ili lukova ili linija, koji su 2-elementni podskupovi od V (npr. ivica je povezana sa dva tjemena, a relacija je predstavljena kao neporedani par tjemena s obzirom na određene ivice). Da bi se izbjegla dvosmislenost, ova vrsta grafikona se može opisati upravo kao neusmjeren i jednostavan.

Drugi smisao grafikona proističe iz različitih koncepcija ivice skupa. U općenitijem smislu,[3] V je skup zajedno sa relacijama događaja koji su povezani sa svakom ivicom dva tjemena. U drugom uopćenom smislu, E je multiskup neporedanih parova (ne nužno različitih) tjemena. Većina autora zovu ovaj tip objekta multigrafikon ili pseudografikon.

Tjemena koja pripadaju ivici se zove krajevi ili krajevi čvorova ruba. W tjeme može postojati u grafikonu i ne pripadati ivici.

V i E se često uzimaju ograničenim, i većina od dobro poznatih rezultata nisu istiniti (ili su radije različiti) za neograničene grafikone jer većina argumenata pada pod ograničen slučaj. Red grafikona je |V|, njegov broj tjemena. Veličina grafikona je |E|, njegov broj ivica. Stepen ili valencija tjemena je broj ivica koje se na to spajaju, gdje se ivica koja spaja tjeme sa sobom (petlja) broji dvaput.

Za ivicu {x, y}, teoretičari grafikona često koristi nešto skraćenu notaciju xy.

Reference[uredi | uredi izvor]

  1. ^ Iyanaga and Kawada, 69 J, str. 234
  2. ^ Biggs, str. 4.
  3. ^ Graham et al., p. 5.

Vanjski linkovi[uredi | uredi izvor]


E-to-the-i-pi.svg Nedovršeni članak Teorija grafikona koji govori o matematici treba dopuniti. Dopunite ga prema pravilima Wikipedije.