Gráfelméleti alapfogalmak

A gráf csúcsokból és az azokat összekötő élekből áll.

Összefüggő gráf: Ha bármely csúcsból az élek mentén bármelyik másik csúcsba el tudunk jutni.

Fokszám: Megmutatja, hogy az adott csúcsból hány darab él indul ki.

Kör: Élek olyan sorozata, mely csupa különböző csúcsokon áthaladva, visszavezet a kiinduló csúcshoz.

Fa: Olyan összefüggő gráf, amelyben nincs kör. (Ekkor bármelyik csúcsból bármelyik csúcsba csak egyféleképpen juthatunk el.)

Az élek száma fele annyi, mint a csúcsok fokszámának összege. = A csúcsok fokszámának összege duplája az élek számának.

Ez utóbbi megfogalmazásból következik, hogy a csúcsok fokszámának összege mindig páros.

Egy szuper kis összefoglaló a gráfokról:
https://www.mateking.hu/kozepiskolai-matek/grafok/minden-amit-a-grafokrol-tudni-erdemes#1
A gráfokat sok helyen használják, ahol költségeket kell számolni:
http://juhaasztamaas.uw.hu/1213/11G1_halo/utvalasztas.html

Jó kis feladatok gyűjteménye
https://wm-iskola.hu/sites/all/files/prints/wm_j1j_matek_10_grafok.pdf

Gazsi ismeri Dzsenifert. Vilma és Irma ismerik egymást. Taksony mind a négy embert ismeri. Ábrázold gráffal az ismeretségeket, ha tudjuk, hogy az ismeretségek kölcsönösek!

Rajzolj olyan gráfot, melyben a csúcsok fokszámai rendre
a) 4, 3, 3, 1, 2, 1!
b) 3, 3, 2, 2, 1!

Andrea, Balázs, Csaba, Dia és Erika egy nyelvtanfolyamra jár. Tudjuk, hogy Andrea 3 társa mellett, Balázs, Csaba és Dia pedig 2-2 társa mellet ült már valamelyik órán.
Hány ember mellett ült eddig Erika? Szemléltesd gráffal!

Adott 7 település, melyek neve után egy szám jelzi, hogy az adott településről hány közvetlen buszjárat indul az adott települések közül egy másikra.
Alkuhely-2, Bazárda-1, Csóriság-1, Dorgálda-1, Ezeknek-2, Főhely-4, Gözdömics-1
Tudjuk még, hogy Ezeknekről van közvetlen járat Főhelyre. Ábrázold a települések közötti buszközlekedést gráffal!

Lehetséges-e, hogy egy 5 fős társaságban mindenki 3 embert ismer?

Egy társaságban mindenki mindenkivel kezet fogott, s így minden ember 5-ször parolázott. Hány fős a társaság? Hány kézfogás történt összesen?

Egy sakkversenyen 10-en indulnak. Mindenki mindenkivel játszik egyszer. Balambér már játszott Ödönkével, Zsigával és Lukréciával. Zsiga túl van a Timotival, Gedeonnal és Irmával való partikon. Ödönke megverte Irmát és remizett Sanyival. Hány játszma van még hátra?

Rajzolj egy olyan hatpontú gráfot, melyben a pontok fokszámának összege 14!