Hirdetés

Gráfelmélet

3 perc olvasás
Gráfelmélet

Ha adott egy V ponthalmaz és egy E élhalmaz, amely V-beli pontpárokat tartalmaz, akkor a V és E által létrejött struktúrát gráfnak nevezzük. Jelölése G(V,E). A gráfokat szemléletesen síkbeli ponthalmazokként ábrázoljuk, ahol bizonyos pontokat vonallal vagy görbével összekötünk.

Hirdetés

Beszélhetünk irányított és irányítatlan gráfokról aszerint, hogy az éleiknek adunk-e irányítást, vagy nem.

Ha egy él kezdő- és végpontja is ugyanaz a pont, akkor az élet hurokélnek nevezzük. Ha két él ugyanaz a két pontot köti össze, akkor többszörös élekről beszélünk.

Egyszerű gráfoknak nevezzük azokat a gráfokat, amelyekben nincs hurokél és többszörös él.

Két él szomszédos, ha közös pontból indulnak ki. Két pont szomszédos, ha őket él köti össze.

Hirdetés

Egy gráf összefüggő, ha bármely pontjából bármely másikba el lehet jutni szomszédos gráfbeli élek egy sorozata mentén.

Egy csúcs fokszáma egyenlő a csúcsba futó élek számával.

Izolált csúcsnak hívjuk azokat a csúcsokat, amelyekbe nem fut él, tehát a nulla fokszámú csúcsokat.

Tétel: Bármely véges gráfban a fokszámok összege az élek számának kétszeresével egyenlő.

Bizonyítás: A fokszámok összegének képzésénél minden élet kétszer számolunk, a két végpontjánál.

Hirdetés
Még 199 szó van a tételből!
A tartalom teljes megtekintéséhez kérlek lépj be az oldalra, vagy regisztrálj egy új felhasználói fiókot!

Címkék: végpont


Iratkozz fel hírlevelünkre

Értesülj elsőnek a legújabb minőségi tételekről, jegyzetekről és az oldal új funkcióiról!

Sikeres feliratkozás

Valami hiba történt!