eMatematikas Prisijunk Forumas VBE užduotys ONLINE testai

Grafas. Įrodykite, kad galime viršūnes nuspalvinti dviem spalvomis


Turime baigtinį grafą (n viršūnių ir b jas jungiančių briaunų). Kiekviena briauna jungia dvi viršūnes. Įrodykite, kad galime viršūnes nuspalvinti dviem spalvomis taip, kad bent pusė briaunų jungtų skirtingų spalvų viršūnes.


Pataisymas: Sąlyga buvo performuluota. Uždavinys nepasikeitė.

pakeista prieš 14 m

Pirmas būdas.
Jei viršūnės kokiu nors būdu nuspalvintos, tegu V būna skaičius briaunų, jungiančių vienodos spalvos viršunes, o S būna skaičius briaunų, jungiančių skirtingos spalvos viršūnes. Pažymėkime T = S - V. Mūsų tikslas rasti tokį nuspalvinimą, kad T >= 0.
Iš pradžių nuspalvinkime visas briaunas viena spalva. Tuomet S = 0, V = b ir T = -b.
Dabar įrodysime kertinį pastebėjimą: jei viršūnės nuspalvintos taip, kad T < 0, tai galime rasti viršūnę, kurios daugiau nei pusė jungčių jungia ją su tos pačios spalvos viršūnėmis. Iš tiesų, tegu v_i būna skaičius briaunų, jungiančių viršūnę i su tos pačios spalvos viršūnėmis, tegu s_i būna skaičius briaunų, jungiančių virūnę i su priešingos spalvos viršūnėmis ir tegu t_i = v_i - s_i. Aišku, kad v_1 + v_2 + ... + v_n = 2V, s_1 + s_2 ... + s_n = 2S, taigi 0 > 2T = 2S - 2V = (s_1 - v_1) + (s_2 - v_2) + ... + (s_n - v_n) = t_1 + t_2 + ... t_n. Kadangi suma t_1 + ... + t_n neigiama, tai bent vienas t_i neigiamas ir viršūnė i yra tokia, kokios ieškome.
Taigi viršūnės kažkaip nudažytos, žinome S, V ir T = S - V < 0, o viršūnė i turi daugiau jungčių su tos pačios nei priešingos spalvos viršūnėmis (t.y. s_i - v_i = t_i < 0). Perdažykime ją kita spalva. Kokie bus atitinkami skaičiai S', V', T' = S' - V' šiam perdažymui? S' = S + v_i - s_i, V' = V + s_i - v_i (nes v_i vienspalvės briaunos tapo dvispalvėmis, o s_i dvispalvės tapo vienspalvėmis), taigi T' = T + 2(v_i - s_i) = T - 2t_i. Kadangi t_i <= -1, tai T' >= T + 2.
Ką mes įrodėme? Kad jei viršūnės nuspalvintos taip, kad T < 0, mes galime perdažyti vieną viršūnę taip, kad T padidėtu bent dviems. Tačiau pradiniame nudažyme turėjome T = -b. Taigi atlikę ne daugiau nei b/2 perdažymų, gausime nudažymą, kuriam T >= 0 - mes tokio ir ieškojome.
Antras būdas.
Nuspalvinkime viršūnes atsitiktinai. Kokia tikimybė, kad konkreti briauna bus dvispalvė? Iš viso yra 2^n nuspalvinimo būdai ir 2^(n-1) iš jų briauna dvispalvė. Taigi tikimybė 1/2. Kokia dvispalvių briaunų skaičiaus matematinė viltis? Tarkime, kad S yra dvispalvių briaunų skaičius, S_i = 1 arba 0 priklausomai nuo to, ar briauna i dvispalvė, ar ne. E S = E (S_1 + S_2 + ... + S_b) = E S_1 + E S_2 + ... + E S_b = 1/2 + ... + 1/2 = b/2. Dabar sunumeruokime nuspalvinimus N_1, N_2, ..., N_2^n. Visi jie vienodai tikėtini (konkretaus nuspalvinimo tikimybė 1/2^n). Tegul D(j) būna dvispalvių briaunų skaičius j-tajame nuspalvinime. Tuomet E S = 1/2^n (D(1) + D(2) + ... + D(2^n)) ir žinome, kad E S = b/2. Taigi D(j) >= b/2 su bent vienu j. Tą ir reikėjo įrodyti.

Nori sudalyvauti šioje temoje ir parašyti savo pranešimą? Prisijungti »