Gráfelméleti alapok

• Egyszerű gráf
• Egyszerű gráfok megadása: grafikus ábrázolás, szomszédsági mátrix, pont-él illeszkedési mátrix.
• Fokszám
• Pontok elhagyása, élek elhagyása egy egyszerű gráfból.
• Részgráf, feszített részgráf, feszítő részgráf egyszerű gráfokban.

• Hurokél-nélküli gráfok.
• Párhuzamos élek.
• Hurokél-nélküli gráfok megadása: grafikus ábrázolás, szomszédsági mátrix, pont-él illeszkedési mátrix.
• Fokszám
• Pontok elhagyása, élek elhagyása egy hurokél-nélküli gráfból.
• Részgráf, feszített részgráf, feszítő részgráf hurokél-nélküli gráfokban.

• Gráf
• Hurokélek.
• Gráfok megadása: grafikus ábrázolás, szomszédsági mátrix, pont-él illeszkedési mátrix.
• Fokszám
• Pontok elhagyása, élek elhagyása egy gráfból.
• Részgráf, feszített részgráf, feszítő részgráf gráfokban.

Az első gráfelméleti tételünk: Minden gráfban a fokszámok összege az élszám kétszerese.

Ennek több következménye van:

1. Következmény: Egy gráf fokszámainak összege páros.

2. Következmény: Egy gráf páratlan fokú pontjainka száma páros.

3. Következmény: Ha egy gráfban van egy páratlan fokú pont, akkor van legalább egy másik ilyen csúcs is.

• Irányított gráf
• Irányított gráfok megadása: grafikus ábrázolás, szomszédsági mátrix, pont-él illeszkedési mátrix.
• Fokszám
• Pontok elhagyása, élek elhagyása egy irányított gráfból, részgráf, feszített részgráf, feszítő részgráf irányított gráfokban definíciója analóg a gráfokesetéhez. Megfogalmazásuk feladat a hallgató számára.

Tétel: Egy irányított gráfban a kifokok összege ugyanakkora mint a befokok összege. A két összeg közös értéke az irányított gráf élszáma.

• Graph Theory Glossary  (Maintained by Chris Caldwell)
• Graph Theory Tutorial  (Maintained by Chris Caldwell)
• Graph Theory Lessons  (Maintained by P. Mawata)
• Graph Theory  (Mathmania)