Gráf

Mit nevezünk gráfnak? Mi az n pont teljes gráf? Mi az egyszerű gráf? Mi az összefüggő gráf?

Ha véges sok adott pont közül egyeseket vonallal összekötünk, akkor a kapott ábrát gráfnak nevezzük. A pontok a gráf pontjai vagy szögpontjai, a vonalak a gráf élei.

Ha egy gráfnak n pontja van [n pozitív egész szám], és mindegyik pontból pontosan 1 él vezet a többi ponthoz, akkor a gráfot n pont teljes gráfnak nevezzük.

A gráfokban előfordulhat olyan él is, amelynek mindkét végpontja ugyanaz a pont. Az ilyen él neve hurok. Két csúcsa között több élt is húzhatunk, ezek a többszörös élek.

Egy gráfot egyszerűnek nevezünk akkor, ha nincs benne sem hurok, sem többszörös él.

A gráf összefüggő, ha bármely pontjából bármely másik pontjába élek mentén el lehet jutni.