Matematikában jártas embertől kérnék segítséget. Középiskolai versenyfeladatban jártas valaki?

Ez a feladat kombinatorikával oldható meg. Leginkább az ismétlés nélküli kombináció kell hozzá: tudod, n alatt a k, úgy fogom jelölni, hogy (n alatt k)

Az egyszerű gráf azt a három dolgot jelenti, hogy

- élei nem irányítottak

- nincs benne hurokél, tehát nincs olyan él, aminek az eleje és vége ugyanaz a csúcs

- két csúcs között csak egyetlen él lehet max.

6 csúcs esetén lehet összesen 6·5/2 darab él. Ezt kétféleképpen is be lehet látni:

a) Bármelyik csúcsból húzhatsz 5 élet a többi csúcsba (nincs hurokél, tehát saját magába nem), ez 6·5 él lenne, de így minden élet kétszer számolnál: akkor is, amikor A-ból B-be megy, meg akkor is, amikor B-ből A-ba. Ezért kell 2-vel osztani

b) Egy él két csúcs között lehet. A 6 csúcsból (6 alatt 2) féleképpen tudunk kiválasztani kettőt, hogy hol menjen él. Ennyi él lehet tehát összesen.

Tehát lehet maximum 6·5/2 = 15 él. Ebből 5 élet (15 alatt 5) féleképpen tudunk kiválasztani.

Azt hiszem, ez a válasz a kérdésre, nem kell tovább számolni. Tudd viszont, hogy csak akkor ez a válasz, ha a csúcsok meg vannak jelölve (erről nem írtál). Ha nincsenek megjelölve, akkor sok gráf lehet azonos (izomorf) ebből a (15 alatt 5)-ből, ha átrendezzük a csúcsokat. Azt hiszem, akkor teljesen máshogy kellene a problémához hozzáállni.

#8 Feltételezem a gráfelméletben a "különböző" nem izomorfat jelent. Különben úgy is lehetne érteni a feladatot, hogy a gráf pontjai a sík pontjai és rögtön végtelen sok lehetőség van. A csúcsok és élek neve nem gráfelméleti tulajdonság.

A kérdezőnek: az alapvető probléma az, hogy ezekhez a feladatokhoz már valamilyen szintű matematikai gondolkodásra van szükség, nem betanult módszerek sorozata. Ezt nem fogja neked senki megtanítani egy-két perc alatt.

(Nincs neved, ezért csak #9-nek hívlak.)

#9: De, izomorfizmusnak hívják a gráfok azonosságát is. A "végtelen sok lehetőség"-et nem értem, de ne magyarázd meg.

A gráfszámlálásnál a 'labeled' gráfokkal is komolyan foglalkoznak (lásd pl. Harary, Palmer: Graphical Enumeration; az első fejezet csak erről szól.)

Visszatérve a feladatra: A kérdező nem tisztázta végül, hogy mi is pontosan a feladat szövege. Ha csak annyi volt, amit írt, akkor nem cimkézett gráfról van szó, és akkor nem lehet ilyen kombinatorikai megoldást adni. Akkor csak az marad, hogy fel kell rajzolni minden lehetőséget. Nincs sok, csak 15 (lásd A001433 sorozat az OEIS-ben: [link] )

Kérdező, rajzold fel őket. Könnyű kihagyni egyet-kettőt, ezért segítségnek itt van az összes 6 csúcsú gráf:

[link]