Berges lemma - Berges lemma - Wikipedia

Yilda grafik nazariyasi, Berge lemmasi a taalukli M a grafik G bu maksimal (mumkin bo'lgan eng katta qirralarning sonini o'z ichiga oladi), agar yo'q bo'lsa kattalashtirish yo'li (bepul (mos kelmaydigan) tepaliklarda boshlanadigan va tugaydigan va mos keladigan joy ichida emas, balki qirralarning o'rtasida almashinadigan yo'l) bilan M.

Buni frantsuz matematikasi isbotlagan Klod Berge 1957 yilda (garchi allaqachon kuzatilgan bo'lsa ham Petersen 1891 yilda va Knig 1931 yilda).

Isbot

Berge lemmasini isbotlash uchun avvaliga boshqasi kerak lemma. Oling grafik G va ruxsat bering M va M ′ ikki bo'ling taalukli yilda G. Ruxsat bering G ′ natijada bo'ling grafik olishdan nosimmetrik farq ning M va M ′; ya'ni (M - M ′) ∪ (M ′ - M). G ′ quyidagilardan biri bo'lgan bog'langan komponentlardan iborat bo'ladi:

  1. Izolyatsiya qilingan tepalik.
  2. Hatto tsikl uning qirralari o'zgarib turadi M va M ′.
  3. A yo'l uning qirralari o'zgarib turadi M va M ′, aniq uchlari bilan.

The lemma har birini kuzatib isbotlash mumkin tepalik yilda G ′ ko'pi bilan 2 qirraga tushishi mumkin: bittadan M va bittasi M ′. Har bir tepalikning darajasi 2 dan kam yoki unga teng bo'lgan grafikalar izolyatsiyadan iborat bo'lishi kerak tepaliklar, tsikllar va yo'llar. Bundan tashqari, har bir yo'l va tsikl G ′ o'rtasida o'zgarishi kerak M va M ′. A uchun tsikl Buning uchun uning teng sonli qirralari bo'lishi kerak M va M ′va shuning uchun teng uzunlikda bo'lishi kerak.

Keling, buni isbotlaylik qarama-qarshi Berge lemmasi: G bor taalukli dan kattaroq M agar va faqat agar G oshirish yo'liga ega. Shubhasiz, kengaytirish yo'li P ning G ishlab chiqarish uchun ishlatilishi mumkin taalukli M ′ bu kattaroqdir M - faqat oling M ′ bo'lish nosimmetrik farq ning P va M (M ′ ning aynan shu qirralarini o'z ichiga oladi G aniq birida paydo bo'ladi P va M). Demak, teskari yo'nalish amal qiladi.

Oldinga yo'nalish uchun, ruxsat bering M ′ bo'lishi a taalukli yilda G dan kattaroq M. Ko'rib chiqing D., ning nosimmetrik farqi M va M ′. Shunga e'tibor bering D. yo'llardan va hatto tsikllar (avvalgi kuzatilganidek lemma ). Beri M ′ dan kattaroqdir M, D. dan ko'proq qirralarga ega bo'lgan komponentni o'z ichiga oladi M ′ dan M. Bunday komponent - bu yo'l G dan boshlanib, chekka bilan tugaydi M ′, demak, bu kengaytirish yo'li.

Xulosa

Xulosa 1

Ruxsat bering M maksimal mos keladigan bo'ling va o'zgaruvchan zanjirni ko'rib chiqing, shunday qilib yo'lning qirralari mavjud bo'lish va bo'lmaslik o'rtasida o'zgarib turadi M. Agar o'zgaruvchan zanjir a bo'lsa tsikl yoki a yo'l teng uzunlik, keyin yangi maksimal moslik M ′ ichida joylashgan qirralarni almashtirish orqali topish mumkin M va emas M. Masalan, o'zgaruvchan zanjir (m1, n1, m2, n2, ...), qaerda mmen ∈ M va nmen ∉ M, ularning o'rnini bosish hamma narsani amalga oshiradi nmen yangi mos keladigan qism va barchasini qiling mmen mos keladigan qism emas.

Xulosa 2

Agar chekka maksimal moslikka tegishli bo'lsa, lekin barcha maksimal mosliklarga tegishli bo'lmasa, chekka "erkin" hisoblanadi. Bir chekka e o'zboshimchalik bilan maksimal darajada mos keladigan bo'lsa, faqat bepul M, chekka e mos kelmaydigan tepadan boshlanadigan yoki o'zgaruvchan o'zgaruvchan yo'lga tegishlidir tsikl. Birinchi natija bo'yicha, agar chekka bo'lsa e bunday o'zgaruvchan zanjirning bir qismi, keyin yangi maksimal moslik, M ′, mavjud bo'lishi kerak va e ham mavjud bo'lar edi M yoki M ′va shuning uchun erkin bo'ling. Aksincha, agar chekka bo'lsa e bepul, keyin e maksimal darajada mos keladi M lekin emas M ′. Beri e ikkalasining ham qismi emas M va M ′, u olganidan keyin ham mavjud bo'lishi kerak nosimmetrik farq ning M va M ′. The nosimmetrik farq ning M va M ′ natijalar a grafik izolyatsiya qilingan tepaliklardan, hatto o'zgaruvchan tsikllardan va o'zgaruvchan yo'llardan iborat. Deylik, aksincha e toq uzunlikdagi ba'zi bir yo'l komponentlariga tegishli. Ammo keyin ulardan biri M va M ′ ushbu komponentda ikkinchisiga nisbatan bir chekka kamroq bo'lishi kerak, demak, komponent umuman olganda, mos keladigan narsaga nisbatan oshirish yo'lidir. Asl lemma bo'yicha, bu mos keladi (bo'lsin M yoki M ′) maksimal darajada mos kelishi mumkin emas, bu ikkalasining taxminiga ziddir M va M ′ maksimal. Shunday qilib, beri e har qanday toq uzunlikdagi yo'l komponentasiga tegishli bo'lishi mumkin emas, u o'zgaruvchan tsiklda yoki juft uzunlikda o'zgaruvchan yo'lda bo'lishi kerak.

Adabiyotlar

  • Berge, Klod (1957 yil 15 sentyabr), "Graf nazariyasidagi ikkita teorema" (PDF), Amerika Qo'shma Shtatlari Milliy Fanlar Akademiyasi materiallari, 43 (9): 842–844, doi:10.1073 / pnas.43.9.842, PMC  534337, PMID  16590096.
  • G'arbiy, Duglas B. (2001), Grafika nazariyasiga kirish (2-nashr), Pearson Education, Inc., 109-110 betlar, ISBN  81-7808-830-4.
  • Berge, Klod (1973), Grafika va gipergrafalar, North-Holland nashriyot kompaniyasi, 122–125-betlar, ISBN  0-444-10399-6.