Graf turneu

[Vlad Matei]

La un turneu de ping-pong cei \( n\geq 2 \) participanti joaca, fiecare cu fiecare, exact cate un meci. Sa se arate ca exact una dintre urmatoarele doua situatii se realizeaza la sfarsitul turneului:
1) Cei \( n \) participanti pot fi etichetati cu numerele \( 1,2,\dots,n \) astfel incat \( 1 \) a batut pe \( 2 \), \( 2 \) a batut pe \( 3 \), etc si \( n \) a batut pe \( 1 \).
2) Participantii pot fi partitionati in doua submultimi nevide \( A \), \( B \) astfel oricare din \( A \) a batut pe oricare din \( B \).

Stelele matematicii, 2007

[Filip Chindea]

Un graf turneu \( G(V, E) \) are fie proprietatea ca este hamiltonian, fie ca exista o partitie \( V = A \cup B \), \( V \notin \{A, B\} \) astfel încât pentru orice \( x \in A \) si \( y \in B \), are loc \( xy \in E \).

Stelele matematicii, 2007

Solutie. Evident cele doua situatii nu se realizeaza simultan. Presupunem ca \( G \) nu este hamiltonian; fie \( P = x_0...x_{k-1}x_0 \) ciclul de lungime maximala, deci \( k + 1 \le n := |V| \). Fie acum un \( y \in V \backslash V(P) \). Daca exista \( i \in \overline{0, k-1} \) cu \( x_iy \in E \), atunci \( x_{i+1}y \in E \) (altfel ciclul \( x_0...x_iyx_{i+1}...x_{k-1}x_0 \) ar contrazice maximalitatea lungimii lui \( P \)). Inductiv rezulta ca \( x_ty \in E \) pentru orice \( t \in \overline{0, k-1} \). Astfel putem scrie \( V \backslash V(P) = S \cup T \), cu \( S, T \) disjuncte (nu neaparat nevide), astfel încât pentru orice \( x \in V(P) \), \( y \in S \), \( z \in T \), are loc \( \{xy, zx\} \subset E \). Daca prin absurd ar exista \( y \in S \), \( z \in T \) cu \( yz \in E \), \( x_0yzx_1...x_{k-1}x_0 \) genereaza o contradictie asupra maximalitatii lungimii lui \( P \). Finalizarea se face alegând \( A = V(P) \cup T \) si \( B = S \) (daca \( S \) este vida putem alege \( A = T \) si \( B = V(P) \)).

Nota. Toate muchiile si ciclurile sunt orientate (adica, pentru comoditate, am notat \( xy := (x, y) \)). De asemenea \( V(P) \) este multimea vârfurilor drumului \( P \). Cazurile particulare/triviale plus detaliile sunt lasate cititorului.

Remarca. Un corolar binecunoscut al acestei probleme este urmatorul:
Orice graf turneu este tare conex daca si numai daca este hamiltonian.