300000
Oʻrgimchak tarmogʻi©
G'alabalarning umumiy soni: 143677
| (6 – 20): | Davr Yoʻl Tasodifiy Qiyinchilik |
Ta'riflar + Qanday qilib bu hali ham "matematik" o'yin?
Ushbu o'yindagi diagrammalar graf nazariyasi deb nomlanuvchi matematika sohasiga asoslangan!
Grafik nima?
Grafik: Grafik tugunlar va qirralardan iborat.
Node: Grafikni bog'laydigan "ob'ektlar" tugunlar deb ataladi. O'rgimchak tarmog'ida tugunlar doiralardir.
Edge: Chekka - bu ikki tugun orasidagi grafikdagi ulanish. O'rgimchak tarmog'ida qirralar chiziqlardir.
Yoʻlni uzaytirish
Yo'l: Yo'l - boshlang'ich tugun va yakuniy tugunlari bilan bog'langan qirralarning ketma-ketligi.
Eulerian Path: Bu grafikdagi har bir qirrani aynan bir marta ishlatadigan yo'l.
Ushbu o'yindagi maqsad Eulerian yo'lini topishdir.
Kundalik hayotda Eulerian yo'llari qanday?
Qor mashinasi, ko'chani tozalash yuk mashinasi va pochtachi har bir ko'chadan o'tishi kerak, ammo ko'chadan ikki marta o'tmaslikni istagan mashinalar va odamlarga misoldir.
"Euler" nomi tanishmi?
Graflar nazariyasi matematik Leonhard Euler shu kabi yo'llar ustida ishlayotgan paytda boshlangan.
Euler Königsbergning etti ko'prigi to'g'risida har bir ko'prikdan aniq bir marta o'tib bo'lmasligini isbotlagan maqola yozdi.
Bu haqda ko'proq ma'lumot olish uchun quyidagi muammo xaritasini bosing.
Tsikl: Tsikl - boshlagan tugunda tugaydi yo'l.
Eulerian Cycle: Bu Eulerian yo'li, u ham tsikl. Yuqoridagi o'yinimizda "Tsikl" ni tanlang va echim har doim Eulerian tsikli bo'ladi!
O'yin sozlamalari ko'rsatmalari
Tugunlar yonidagi matn maydonida 6-20 orasida istalgan raqamni kiritishingiz mumkin. Bu raqam grafikda ko'rsatilgan tugunlar soni bo'ladi. Raqam qancha ko'p bo'lsa, echim shunchalik qiyin bo'ladi!
Keyin, grafig turini tanlang
Tsikl: G'alaba qozongan yo'llar har doim ular boshlagan tugunda tugaydi.
Yo'l: G'alaba qozongan yo'llar ular boshlagan tugunda tugamaydi.
Tasodifiy: Euler tsikli yoki Eulerian yo'liga ruxsat berishi mumkin bo'lgan grafiklar. G'alaba qozongan yo'llar ular boshlagan tugunda tugashi mumkin yoki bo'lmasligi mumkin.
Qiyinchilik: Qirralar kesib o'tadigan qo'lda ishlangan grafiklar va shuning uchun ko'priklarni aniqlash aniq emas.
Nihoyat, grafik sozlamalaridagi o'zgarishlarni ko'rish uchun "Yangi veb yaratish" -ni bosing!
Avval qaysi tuguni tanlashim kerak?
Daraja: Daraja tugunning xususiyatidir. Unga ulangan qirralarning soni. Biz ularning darajasiga qarab toq darajali tugunlar va teng darajali tugunlarni ajratamiz.
Bog'langan grafik: Har bir tugun jufti yo'l orqali ulanishi mumkin bo'lgan grafik.
Ko'prik: Agar qirraning ikki uchi boshqacha tarzda ulanmasa, chekka ko'prikdir. Shunday qilib, ko'prikni kesib o'tgandan so'ng, oldingi tomonga qaytib bo'lmaydi. Ko'prikni olib tashlash grafikni ikki uzilgan komponentga ajratadi.
Yo'naltirilmagan grafik : qirralarning yo'nalishi biriktirilmagan grafik. Biz faqat ushbu o'yinda bo'lganlarni ko'rib chiqamiz.
Yo'naltirilgan grafik : Har bir chekkaning bir tomonlama ko'cha kabi biriktirilgan yo'nalishi bo'lgan grafik.
Yo'naltirilmagan grafikda Euler tsikli mavjud bo'lganda barcha tugunlar teng darajaga ega (0, 2, 4, 6 daraja...). Ular uchun boshlang'ich tugun sifatida har qanday tugunni tanlashingiz mumkin va baribir g'alaba qozonishingiz mumkin. Siz boshlagan tugunda tugatishingiz kerakligini yodda tuting.
Grafikda Euler yo'li mavjud, lekin emas Euler tsikli, aynan ikkita tugun toq darajaga ega (1, 3, 5, 7 daraja...) va boshqa barcha tugunlar teng darajaga ega. Bunday holda, boshlang'ich tuguningiz sifatida toq darajali tugunni tanlashingiz kerak aks holda Eulerian yo'lini yakunlay olmaysiz.
Nima uchun aniq ikkita tugun?
Har bir harakatni siz kelgan tugunning tashqarisida" va siz sayohat qilgan tugunga "kirish" deb o'. Ko'pgina tugunlar ushbu juftlik shakliga amal qiladi, shuning uchun ular teng darajaga ega bo'ladi.
O'yinni boshlaganingizda, siz belgilagan birinchi chekka boshlang'ich tugunning "tashqarisida" harakatdir. Bu siz o'yinni o'ynayotganingizda juftlashtirilmagan bo'lib qoladi.
Eulerian tsiklini yaratish uchun siz belgilagan yakuniy qirrasi boshlang'ich tugunga "in" harakatidir. Bu birinchi harakat bilan juftlikni yaratadi, ya'ni boshlang'ich tugun teng darajaga ega.
Agar grafikning Eulerian yo'li tsikl bo'lmasa, siz belgilagan yakuniy qirrasi boshlang'ich tugun bo'lmagan tugunga "in" harakatidir. boshlang'ich tugun toq daraja bilan qoladi va tugun ham toq darajaga ega bo'ladi.
Boshqa holatlar haqida qayg'urmang. Agar toq darajali tugunlar soni to'liq 0 yoki 2 bo'lmasa, Eulerian yo'llari va Eulerian tsikllari bo'lmaydi, ya'ni g'alaba qozonishning hech qanday usuli yo'q. Bu kabi grafiklar bu o'yinda paydo bo'lmasligi kerak.
Dastlabki savollar
Odd darajaga ega tugunlarning toq soni bo'lishi mumkinmi?
Yo'q.
Nima uchun?
Isbot:
Barcha qirralarning barcha uchlarini hisoblash barcha tugunlarning barcha darajalarini qo'shish bilan bir xil raqamni beradi, rozi bo'ldingizmi?
Har bir qirraning 2 uchi bo'lgani uchun, barcha qirralarning umumiy soni teng bo'lishi kerak. (Juft sonlarni qo'shish juft sonni beradi.)
Barcha tugunlarning darajalarini qo'shish uchun juft darajalarni qo'shish va toq darajalarni qo'shish mumkin.
Agar toq darajali tugunlarning toq soni bo'lsa, bu summa toq bo'ladi va keyin hatto + toq = toq, shuning uchun darajalarning umumiy soni toq bo'ladi. Lekin u barcha qirralarning barcha uchlarining umumiy soniga teng va bu teng. Shuning uchun toq darajali tugunlarning soni toq bo'lishi mumkin emas, u teng bo'lishi kerak .
Masalan, 1 - toq son, shuning uchun faqat 1 toq darajali tugunli grafik yo'q.
Eulerian yo'li yoki tsikli qachon mavjud?
Agar tugun teng darajaga ega bo'lsa, ya'ni 2, 4, 6,... qirralar tugunga biriktiriladi, keyin bu tugunga kelganda, foydalanilmagan qirralarning toq soni qoladi, bu noldan katta, shuning uchun bu tugunni tark etib, davom ettirish mumkin. Agar daraja toq bo'lsa, ya'ni 1, 3, 5,.. qirralar biriktirilgan, keyin yo'lni ushbu tugundan boshlash kerak yoki yo'l bu tugunda tugaydi. Yo'lning faqat 2 uchi bo'lganligi sababli, toq darajali faqat 2 tugun bo'lishi mumkin. Shuning uchun:
Eulerian tsikliga ega bo'lish uchun grafikda faqat teng darajali tugunlar bo'lishi kerak, Euler yo'liga ega bo'lish uchun esa 2 ta to'q darajali tugunlar bo'lishi kerak, bitta tugun boshlang'ich va biri yo'lning oxiri bo'ladi.
Eulerian yo'li yoki tsiklini qanday topish mumkin?
Yuqorida ko'rsatilganidek, agar g'alati darajadagi tugunlar bo'lmasa, u holda har qanday tugundan boshlanishi mumkin va xuddi shu tugunda tugaydi. Agar aniq 2 ta to'q darajali tugunlar mavjud bo'lsa, unda ushbu 2 tugunlardan birida boshlanishi kerak va avtomatik ravishda ikkinchisida tugaydi.
Yo'lni uzaytirishda biror narsa noto'g'ri bo'lishi mumkinmi?
Ha, biror narsa noto'g'ri bo'lishi mumkin. Misol:
2 4 / \ / \ 1---3---5
Barcha tugunlarning darajasi 2 darajali 3 tugundan tashqari 4. Shunday qilib, barcha darajalar teng va biz har qanday joydan boshlashimiz mumkin. Keling, 1 tugundan boshlaylik va 3 tuguniga o'taylik va o'tgan barcha qirralarni tashlaylik.
2 4 / \ / \ 1 3---5
Chet 3-2 ko'prik bo'ladi. Bu qirrani kesib o'tish va olib tashlash 3-2 uzilgan grafikni hosil qiladi
2 4 / / \ 1 3---5
endi to'liq o'tib bo'lmaydi. Shuning uchun Euler tsiklini yakunlash uchun 3 dan 4 yoki 5 ga davom etish kerak.
Ko'prikdan o'tishni qanday oldini olish mumkin?
Chekkaning ko'prik ekanligini tekshirish uchun chekkaning bir uchidan boshlanib, barcha qo'shni tugunlarini va barcha qo'shnilarini va boshqalarni ziyorat qilish kerak. Agar chekkaning boshqa tomoniga etib borilmasa, chekka ko'prikdir. Barcha qo'shnilarni bunday to'liq qidirish unchalik qimmat emas. Ammo agar har bir chekkani kesib o'tishdan oldin buni qilish kerak bo'lsa, unda umumiy harakat katta. To'liq algoritm 1883 yildan beri Fleury algoritmi deb nomlanadi.
Samaraliroq algoritm bormi?
Yanada samarali algoritm Hierholzer (1873).
Agar grafikda 2 ta toq darajali tugunlar bo'lsa, unda yo'lni topadi, aks holda tsikl, har ikkala holatda ham ko'priklarni tekshirmasdan juda tez.
1) Barcha ishlatiladigan qirralarni olib tashlagandan so'ng, qolgan foydalanilmagan qirralarning darajasi barcha tugunlar uchun hamdir.
Nima uchun?
Agar tugunning darajasi teng bo'lsa, unda u chap bo'lgani kabi tez-tez yaqinlashdi, shuning uchun u hali ham teng. Agar daraja toq bo'lsa, u birinchi yo'lning boshlang'ich tuguni yoki yakuniy tuguni bo'lib, keyin u chap + jami toq sonli marta yaqinlashdi, shuning uchun qolgan daraja toq − odd = even.
2) Ishlatilgan va foydalanilmagan qo'shni qirralarga ega bo'lgan kamida bitta tugun bo'lishi kerak.
Nima uchun?
Chunki asl grafik bog'langan edi.
1 tufayli ushbu tugunda boshlangan va tugaydigan foydalanilmagan qirralarning aylanishini topish mumkin. Chunki 2) ushbu tsikl ushbu tugunga etib borganda birinchi yo'l / tsiklga kiritilishi mumkin. Hozirgacha foydalanilmagan qirralarning tsikllarining bu joylashtirishi barcha qirralar ishlatilguncha takrorlanadi va shuning uchun barcha qirralarni ishlatadigan Euler yo'li yoki Euler tsikli mavjud.
Ushbu tezroq versiyaning narxi qanday?
Oldingi yo'l / tsiklni eslab qolish kerak, shunda qo'shimcha tsiklni o'z ichiga olishi mumkin.
Misol:
2 4 / \ / \ 1---3---5
Birinchi tsikl 1-3-2-1 bo'lsin. 3 tuguni ushbu tsiklda va foydalanilmagan tsiklda 3-4-5-3 sodir bo'ladi. Biz uni birinchi tsiklga kiritamiz va 1-3-4-5-3-2-1 tsiklini olamiz. Endi foydalanilmagan qirralar yo'q, shuning uchun algoritm bu erda tugaydi, biz Euler tsiklini topdik.
Bizning interfeysimiz yordamida tsiklni qanday kiritish mumkin?
Yuqoridagi 3 tuguni kabi ishlatilgan va foydalanilmagan qirralarning eng so'nggi tuguniga etib borguncha "Bekor qilish" tugmasini bosish mumkin, so'ngra 3-4-5-3 tsiklidan o'tib, keyin bajarilmagan qirralar bilan davom ettirish mumkin.
Agar to'g'ri darajali tugun bo'lsa, bir-biridan ikkinchisiga birinchi yo'lni chizish uchun ikkalasini ham topish kerakmi?
Yo'q. Agar faqat bittasini topsa, u holda yo'lni ushbu tugundan boshlash mumkin va barcha qirralardan foydalanadimi yoki yo'qmi, avtomatik ravishda boshqa toq darajali tugunga tushadi.
Nima uchun?
Chunki teng darajali tugunga kelganida, unda toq sonli biriktirilgan qirralar ishlatilgan.
Nima uchun?
Har safar tugunga kelganida, biri ham tugunni tark etdi, shuning uchun teng sonli qirralar ishlatiladi. Endi biri keladi va teng darajali tugunda bir chekkadan foydalanadi. Shunday qilib, hammasi bo'lib juft daraja tugunidagi qirralarning toq sonini ishlatgan.
Hatto − odd = odd, shuning uchun foydalanilmagan qirralarning toq soni qoladi. Toq son har doim nol emas, shuning uchun ushbu tugunni tark etish uchun ishlatilishi mumkin bo'lgan kamida bitta foydalanilmagan chekka mavjud. Shuning uchun, barcha qirralar ishlatilganmi yoki ishlatilmaganmi, avtomatik ravishda toq darajali tugunda tugaydi.
Sizda bir to'q darajali tugunni qanday topish mumkinligi haqida taklifingiz bormi?
Albatta, har bir tugunning darajasini tekshirish mumkin, toki g'alati darajali tugunni topmaguncha. Mana hisoblamasdan bir yo'l.
Har qanday tugunni tanlash mumkin. Agar uning darajasi g'alati bo'lsa, demak uni topdi. Agar yo'q bo'lsa, unda tsiklni chizish uchun ushbu tugundan boshlanadi. U to'g'ri darajali tugunda tugaydi, keyin to'g'ri darajali tugun topildi yoki boshlang'ich tugunda tugaydi. Agar shunday bo'lsa, unda barcha ishlatiladigan qirralarni e'tiborsiz qoldiradi va yana buni qiladi, ya'ni tugun tanlang va yo'l yoki tsiklni chizish. Bu to'g'ri darajali tugun topmaguncha yoki boshqa foydalanilmagan qirralar yo'q bo'lmaguncha davom etadi. Keyin barcha tugunlar bir teng darajaga ega.
Agar grafik 1 tomonlama ko'chalari bo'lgan shaharga o'xshab qolsa-chi?
Faqat bitta yo'nalishda o'tishi mumkin bo'lgan qirralarga ega grafik yo'naltirilgan grafik deb ataladi. Yuqoridagi dalillardan so'ng, quyidagi 2 bayonotlari aqlga sig'maydi.
Yo'naltirilgan grafik Euler tsikliga imkon beradi, agar va faqat agar har bir tugun uchun chiquvchi qirralarning soni kiruvchi qirralarning soniga teng bo'lsa.
Yo'naltirilgan grafik Eulerian yo'liga ruxsat beradi, agar va faqat agar
• Bir tugun kiruvchi qirralarga qaraganda bitta chiquvchi qirraga ega,
• bitta tugun chiquvchi qirralardan ko'ra bitta kiruvchi qirraga ega va
• Boshqa barcha qirralar bir xil sonli chiquvchi va kiruvchi qirralarga ega.
Follow or subscribe for updates: