Élszínezés 3.
2016-03-13 6:55
Mert szeretjük a szép színes vonalakat...
Nehéz, beküldte:
bolnyi*, szerkesztő: VenczelGy
Van egy 16 szögpontú teljes gráfunk, amelynek minden élét pirosra, kékre, vagy sárgára színezzük. Teljes gráf alatt az összes lehetséges él berajzolását értjük. Vezessük be a következő definíciót: a gráf akkor tartalmaz egyszínű háromszöget, ha van három olyan pontja, amelyek között futó mindhárom él azonos színű.
Színezzük ki úgy a gráf éleit három színnel úgy, hogy a gráf pontosan 8 db egyszínű háromszöget tartalmazzon!
A megoldáshoz nem a színes gráf ábráját várjuk, hanem a színezési módszer pontos leírását, melyből igazolható a 8 db egyszínű háromszög megléte.
