Gráfelméleti alapfogalmak

Egy ​ (a)   gráfban a ​ (b)   összege egyenlő a(z)​ (c)   számának ​ (d)   .

• tetszőleges
• egyszerű
• fa
• összefüggő
• élek
• csúcsok
• fokszámok
• kétszeresével
• háromszorosával
• négyzetével

Egy gráf ​ (a)   , ha nem tartalmaz hurokélt és ​ (b)   .

• egyszerű
• többszörös élt
• összefüggő
• összetett
• fa gráf
• túl sok élt
• izolált pontot
• Euler kört
• kört

Egy gráf ​ (a)   , ha a gráf bármely két csúcsa között ​ (b)   egy él fut.

• teljes gráf
• pontosan
• összefüggő
• fa gráf
• legalább
• legfeljebb

Rakd össze a definíciót!

• Két gráfot izomorfnak nevezünk,

• az egyik gráfban pontosan akkor van él,

• ha csúcsaik megfeleltethetők egymásnak úgy,

• amikor a másik gráfban.

• hogy két csúcs között

A séta ...

• amelyben egy-egy csúcs vagy él

• a gráf éleinek

• egymáshoz csatlakozó sorozata,

• akár többször is szerepelhet.

Az út olyan ​ (a)   , amelyben ​ (b)   ismétlődő ​ (c)   .

• séta
• nincs
• csúcs
• kör
• gráf
• él
• van

A kör olyan ​ (a)   , melynek kezdő és végpontja ​ (b)   , a többi csúcs ​ (c)   ismétlődik

• séta
• azonos
• viszont nem
• út
• gráf
• különböző
• pedig
• hasonló

Egy gráf összefüggő, ha ...

• bármely két csúcsa között van út

• éleinek száma nagyobb, mint n-1

• nincs benne kör

• van benne séta

Egy ​ (a)   gráfot fagráfnak nevezünk, ha ​ (b)   két csúcsa között ​ (c)   egy út létezik.

• egyszerű
• bármely
• pontosan
• összefüggő
• tetszőleges
• legalább
• legfeljebb

Az alábbiak közül melyik igaz a fagráfra?

• összefüggő gráf

• nincs benne kör

• ha elhagyunk belőle egy élt, akkor már nem lesz összefüggő

• ha hozzáveszünk még egy élt, akkor lesz benne kör