Egy összefüggő egyszerű G gráfban pontosan 4 db kör van és nincs olyan él, amelyet több kör is használna. A gráf komplementerének 69-cel több éle van mint G-nek. Mennyi a csúcsok száma?

Ilyen körök csak úgy lehetnek, hogyha a körök csúcsokban vannak összekötve. Például van 4 kör, amiknek egy közös csúcsuk van, mint valami szélforgónak.

Ebben az esetben, ha a gráfnak n darab csúcsa van, akkor 1 csúcsot leszámítva minden csúcs fokszáma 2 lesz, annak az 1 csúcsnak pedig a fokszáma 8, így a fokszámösszeg 2*(n-1)+8 lesz, az élek száma pedig ennek fele, vagyis (n-1)+4=n+3. A feladat azt mondja, hogy a komplementerben ennél 69-cel több él van, vagyis n+3+69=n+72 él.

Egy gráf és annak komplementere mindig a teljes gráfot adják ki, amiről tudjuk, hogy n*(n-1)/2 darab éle van, tehát a G gráf és annak komplementerének éleinek számának összege ennyi kell, hogy legyen, tehát:

(n+3)+(n+72) = n*(n-1)/2, és ez egy másodfokú egyenlet, amit meg tudunk oldani, ennek pozitív megoldása az n=15, tehát az elképzelt felállásban 15 csúcsa van a gráfnak.

A következő lépés, hogy mutatunk egy ilyen gráfot, tehát demonstráljuk, hogy valóban létezik a feltételeknek megfelelő gráf. Ezután azt kell megmutatnunk, hogy általánosságban is így van, tehát az összes gráf, amire igazak a feltételek, mind 15 csúcsból állnak (de az is lehet, hogy nem, és van más megoldás is a feladatra). Nekem egyelőre ennyire futotta.

Az egyes túlbonyolítja és hülyeséget is ír.

Azt írja 4 darab kör van. Na most akkor a 69et el kell osztani 4el, amely 17,25. Ez kerekítve legyen 17.

Ezután ehhez a számhoz fogod hozzáadni a 69et mivel annyival több éle van mint a G-nek. Vagyis a 17nek.

Így kijön a 86.

Ezután ezt megszorzod még 4el és megkapod a megfejtést ami 344 lesz, azaz ennyi a csúcsok száma.

Szívesen.

#2, aki hülyeséget ír, az te vagy...

Már miért kellene a 69-et 4-gyel osztani? Meg aztán az összes többi lépésnek sincs semmi értelme, arról nem is beszélve, hogy a gráf komplementerével nem is foglalkoztál...

És az is igazán érdekelne, hogy szerinted mi a túlbonyolítás az én megoldásomban...

Hirtelen három lehetőséget tudtam elképzelni:

1; Központi csúcsból négy él, ezekhez csatlakozik egy-egy kör (akár több élen keresztül is).

2; A körök egy láncon vannak.

3; Egy központi kör, amihez három másik csatlakozik egy-egy éllel vagy élsorozattal.

Érdemes észrevenni, hogy az első esetben van négy 3-csúcs, egy 4-csúcs, a többi mind 2-csúcs. A másodikban hat darab 3-csúcs lesz, a negyedikben pedig szintén.

Így össze tudod számolni az éleket, valamint a teljes gráf éleit a csúcsok száma alapján, amiből megvan a komplementer élszáma is. Ezután pedig a kapott másodfokő egyenletet megoldod.