Ilyen típusú feladatot hogyan lehet megoldani?

Valóban hiányos a feladat.

Teljes gráfban (n>2) triviálisan teljesül: n(n-1)/2 él, de nyilván kevesebbel kellene megoldani.

Két lehetőségre gondolok:

1) Mi az a minimális élszám, mellyel rajzolható megfelelő gráf?

Vagy

2) Mi az a minimális élszám, amennyit bárhogyan, találomra berajzolva megfelelő gráfot kapunk?

Lényegesen különbözik a két feladat.

Esetleg a szakaszoknak nem szabad metszeniük egymást? (Síkba rajzolható gráf ?)

--------------------------

Az 1) esetre és síkbarajzolható gráfra van egy tippem:

Rajzolunk egy (n-1) oldalú (gráf)kört, majd a megmaradt pontot a kör belsejébe tesszük és összekötjük a kör minden szögpontjával.

Ez 2n-2 szakaszt tartalmaz és teljesíti a feltételt.

(Az ilyen gráfnak neve is van: „kerék” = „wheel”)

Szerintem nem hiányos a feladat, én legalábbis egyértelműen arra gondoltam, amit Fibonacci 1)-nek írt.

Van jobb megoldás: Legyen a gráfban két kitüntetett "csomópont" (a V és W csúcsok), amikkel minden más csúcs össze van kötve. V és W is össze vannak kötve, így összesen 2n-3 él van. Erről az elrendezésről könnyen belátható, hogy teljesíti a feltételt.

Csak be kellene bizonyítani, hogy kevesebb él nem elég, más elrendezés esetén sem.

- n=3-ra teljesül a tétel: 2n-3 = 3 él szükséges, kevesebbel nem oldható meg.

- Tegyük fel, hogy n csúcsra igaz, hogy legalább 2n-3 él kell hozzá. A G gráf legyen pontosan olyan, vagyis 2n-3 élű.

- Adjunk még egy M csúcsot a G gráfhoz. Ekkor M-ből biztos, hogy kell legalább egy él menjen mondjuk X-be. (Persze ez csak akkor elegendő, ha G mindegyik X-től különböző csúcsa össze van kötve X-szel, de ez most lényegtelen.) Viszont 1 él így sem elég, mert ha az M+X párost nézzük, amihez szintén kell lennie egy harmadik csúcsnak, ahhoz a harmadik csúcshoz (mondjuk Y) is kell menjen él M-ből is. Vagyis legalább 2 új élet is hozzá kell adni G-hez M-mel együtt, így az élek száma 2·(n+1)-3. Teljes indukció kész.

- - - - - - -

Az az érzésem, hogy ez a bizonyítás így nem elegendő. Nem vagyok benne biztos, hogy kell még mást is nézni, de azt hiszem, azt az esetet is kell vizsgálni, hogy mi van, ha az MX (vagy MY, mindegy, legyen MX) él hozzáadásával ki tudunk váltani egy másik, eddig meglévő élet; hátha így az élek számának növelése nélkül készíthetjük el a G' gráfot. Mindenféleképpen X-ből induló élet tudunk jó esetben kiváltani, mondjuk az XK élet. Megengedett, hogy az eredeti G esetleges további éleit is átrendezzük közben... Ilyen esetek lehetnek:

- az XK élet azért nem lehetett az eredeti G gráfból elhagyni, mert az X+L csúcs-párhoz tartozott a K csúcs harmadikként úgy, hogy van XK és LK él is, és semmilyen Z≠K csúcsra sincs a XZ + LZ élek közül mindkettő. Ekkor ha az XK élet tényleg kiváltja az XM él, az csak úgy lehet, hogy lett LM él is. Vagyis L=Y. Viszont (és ez az érv most gyenge lábon áll) K=Y kell legyen, mert X és Y a két "csomópont".

- a KX élet azért nem lehetett az eredeti G gráfból elhagyni, mert a K+L csúcs-párhoz tartozott az X csúcs harmadikként úgy, hogy van KX és LX él is, és semmilyen Z≠X csúcsra sincs a KZ + LZ élek közül mindkettő. Ekkor ha a KX élet tényleg kiváltja az MX él, az csak úgy lehet, hogy ... az nem lehet.

Nem tetszik ez, kell legyen valamilyen egyszerűbb bizonyítás.

Úgy látom, az előző javaslatom („kerék” = „wheel”) lényegesen javítható.

Elég lesz a kör minden második élét megtartani.

Lényegében háromszögekből áll a gráf, de minden háromszög egyik csúcsa egyetlen pontba lenne összevonva („virágszirom” avagy „propeller”).

Eszerint:

páros n-re (3n-2)/2

páratlan n-re (3n-3)/2 él szükséges.

Szuper!

Így az is érthető, miért nem sikerült a 2n-3-at bebizonyítanom :)

Az én gondolatmenetemre átfogalmazva:

- Van egy darab csomóponti elem (V), amivel az összes többi össze van kötve. Ez megoldja az A+B párosokhoz (egyik sem azonos V-vel) tartozó harmadik pont feltételét.

- Az A+V valamint a B+V párosokhoz pedig úgy lesz harmadik pont, hogy létezik AB él is. (Ebből lesz az ABV háromszög, vagy "szirom")

(A és B alatt azt értem, hogy minden nem V csúcsnak ('A'-nak) van pontosan egy darab párja ('B'), kivéve, ha páros darab csúcs van V-vel együtt, ekkor az A csúcs kettőhöz is tartozik.)

Az élek száma: n-1 + ⌈(n-1)/2⌉

Ez persze ugyanannyi, mint amit te is írtál.

A tegnapi bizonyítás-kísérletemhez visszatérve, itt éppen az van, hogy az M pont hozzáadásakor, ha eddig V-vel együtt páratlan csúcs volt, akkor az MV él mellett még mondjuk az MA élet is be kell venni.

Ha viszont M előtt páros csúcs volt (V-t is beszámítva), akkor volt egy nem-szirom N csúcs, amihez NV valamint NA élek mentek. Az NA élet ki lehet váltani egy NM éllel, ezért effektíven csak az MV éllel, tehát eggyel nől az élek száma, nem pedig kettővel.

Sajnos annak bizonyításaként, hogy nem lehetne ennél is jobbat csinálni, még ez sem jó.

Közös igyekezetel alakul a megoldás, már csak a kérdező értékelése marad homályban.

Az volt a sejtésem, hogy a („virágszirom/propeller” típusú gráfok adják a megoldást.

Elvileg elképzelhető volna - bár én nem tudom elképzelni - más felépítésű gráf is, de az élek számát

e ≥ (3n-3)/2

már bizonyára nem lehetne csökkentebni.

Ezt megpróbáltam bizonyítani, szerintem sikerült is, de nem bánnám, ha kritikus szemmel átnéznéd a levezetést:

[link]