KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

MBUTTONS

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

A. 508. An induced subgraph \(\displaystyle S\) of the graph \(\displaystyle G\) is called ``dominant'' if every vertex of \(\displaystyle G\), outside \(\displaystyle S\), has a neighbor in \(\displaystyle S\). Does there exist such a graph which has an even number of dominant subgraphs?

Proposed by: László Miklós Lovász, Budapest

(5 points)

Deadline expired on 10 May 2010.


Google Translation (Sorry, the solution is published in Hungarian only.)

Megoldásvázlat. Legyen a gráf G=(V,E), és definiáljunk egy új gráfot. Az új gráf csúcsai legyenek V nemüres részhalmazai. Két részhalmazt akkor kössünk össze, ha diszjunktak, és nem megy él az egyik halmazból a másikba.

Nézzük, mennyi lehet egy H\subsetV részhalmaznak a foka az új gráfban. Ha egy H domináns, akkor minden P pont vagy benne van H-ban, vagy megy él P-ből H-ba. Ez azt jelenti, hogy ha V egy nemüres részhalmaza diszjunkt H-tól, akkor megy belőle él H-ba, tehát semmiképpen sincs összekötve H-val az új gráfban, vagyis egy domináns részhalmaz foka nulla.

Most tegyük fel, hogy H nem domináns. Álljon H1 azokból a pontokból, amelyek nincsenek H-ban, és nem is megy belőlük él H-ba. Ez tehát nem üres. Egy H2\subsetV akkor és csak akkor lesz H-val összekötve, ha H1-nek részhalmaza. Mivel az üres halmaz nincs a csúcsok között, ha H1-ben k pont van, akkor H-nak 2k-1 szomszédja van, ami páratlan, mivel k>0.

Tehát pontosan a nem domináns részhalmazoknak páratlan a foka az új gráfban, így páros sok van belőlük. Az üres halmaz nyilvan sosem domináns, így összesen páratlan sok nemdomináns halmaz van, de összesen páros sok részhalmaz van, tehát páratlan sok domináns részhalmaz van.


Statistics on problem A. 508.
6 students sent a solution.
5 points:Backhausz Tibor, Bodor Bertalan, Nagy 235 János, Nagy 648 Donát.
1 point:2 students.


  • Problems in Mathematics of KöMaL, April 2010

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley