I/4. feladat megoldása:

Ha meg akarjuk keresni azt, ami az elmondott feladatokban közös, érdemes a következőt tennünk: Ábrázoljuk az embereket, a városokat, illetve a telefonállomásokat egy-egy ponttal. Két embert ábrázoló pontot „összekötünk egy éllel” (azaz például egy egyenes szakasszal), ha játszottak egymással (az 1. feladat megfogalmazásában), ha ismerik egymást (az 1a) feladat megfogalmazásában), ha nem ismerik egymást (3a) feladat), illetve ha kezet fogtak egymással (3b )feladat), két várost jelző pontot összekötünk egy éllel, ha van közöttük közvetlen repülőjárat (a 3c) feladat esetében), illetve két telefonállomást jelző pontot összekötünk egy éllel, ha volt közöttük telefonkapcsolat az adott napon. Egyáltalán nem érdekes, hogy milyen alakja van az „élnek”, amellyel a pontokat összekötjük: lehet az él egy egyenes szakasz, de lehet egy görbe is, ennek semmilyen szerepe nincs, csak az számít, hogy „fut-e él” a két pont között vagy sem.

DEFINÍCIÓ:

Az így kapott ábrát – amely tehát pontokból és ezek közül némelyeket összekötő vonalakból áll, ahol a vonal alakjára nem vagyunk tekintettel – gráfnak nevezzük. A pontok a gráf pontjai vagy csúcsai, a csúcsokat összekötő vonalak a gráf élei. A gráfot véges gráfnak nevezzük, ha a pontjainak száma véges.Ha összeszámoljuk, hány él indul ki egy pontból, akkor a kapott szám a pont fokszáma, vagy röviden foka.

A fenti ábrán szereplő gráfnak négy csúcsa van, ezeket 1-től 4-ig számoztuk. Az 1-es pont (csúcs) csak a 3-assal van összekötve, viszont 3-as pont (csúcs) minden más ponttal (csúccsal) össze van kötve. Az 1-es pont fokszáma egy, a 2-esé és a 4-esé ketto, a 3-asé három.Az x ponttal összekötött pontok az x pont szomszédai.

I/4a). feladat:

Fogalmazzuk meg az 1. feladatot és 3a), 3b), 3c) átfogalmazásait gráfelméleti nyelven!

MEGOLDÁS, tovább