gráfelmélet

jún
08

Gráfelmélet A-tól Z-ig

Gráfnak nevezünk olyan (továbbiakban (f,E,V)) hármasokat, ahol E az élek halmaza (edge), V a csúcsok halmaza (vertex), f pedig egy ún. illeszkedési leképezés, ami E-ből {V,V}-be képez. A gráfokat a gyakorlatban rajzzal szemléltetjük, ahol az egyes pontok a csúcsokat, az őket összekötő vonalak az éleket jelentik. Ha egy csúcsot egy él (ún. hurokél) önmagával köt […]

DETAIL

Tételek gráfokra

Minden legalább két csúccsal rendelkező egyszerű gráfban van két azonos fokszámú csúcs. A pontok fokszámainak összege az élek számának kétszerese, ezáltal páros szám. Bizonyítható, mert minden él pontosan két végpontjával meghatározható. Az előbbiek miatt a páratlan fokú tagok száma mindenképpen páros. Egy n pontú teljes gráf éleinek száma n*(n-1)/2. Ebből n*(n-1) a fokszámok összege. Bármely […]

DETAIL

Gráfelmélet GYIK

Mi is az a gráf?A gráf pontok, és azokat összekötő vonalak összessége a síkban. A pontokat csúcspontoknak, a vonalakat éleknek nevezzük. Mi egy csúcspont fokszáma?Egy csúcspont fokszáma meghatározza, hogy oda mennyi él fut be. Mi a teljes gráf?Teljes gráfról beszélünk, ha az összes csúcspont össze van kötve egymással. Ez esetben minden pont fokszáma ugyanannyi. Ez […]

DETAIL