qələmi qaldırmadan bir qutuda x necə ediləcək


cavab 1:

Bəli. İstədikləriniz riyaziyyatda bir

Eulerian Path

kimi tanınan bir riyaziyyat sahəsində öyrənilir

qraf nəzəriyyəsi

. Bununla birlikdə, sualınıza cavab almaq üçün qraf nəzəriyyəsini çox başa düşməyə ehtiyac yoxdur.

Meydanınızdakı dörd nöqtəyə baxın. Kənarları və diaqonallarını çəkməyə çalışdığınız üçün bu nöqtələrin hər birinin içərisindən çıxan / içəri girən tək sayda xətt var. Bir xətti təkrarlamadan kvadratı diaqonallarla uğurla çəkmək üçün (bunu etmək istəmədiyinizi düşünürəm) bir nöqtədən başlamalı, tərk etməli və sonra son nöqtədən başqa digər nöqtələri uğurla ziyarət edib tərk etməlisiniz. tərk etmə. İndi diqqət yetirin, əgər bir nöqtənin tək sayda xətti bağlanmışsa, həm xətləri əhatə edərkən həm ziyarət edə, həm də nöqtəni tərk edə bilməzsiniz. Düşünün. Təsəvvür edin ki, qələmini götürürsən, sətirlərdən birini o nöqtəyə keçir və tərk edirsən - bu iki sətir çəkdi. İndi bir də geri qayıdıb yenidən ayrıldığını təsəvvür edin - iki sətir daha. Beləliklə, tək sayda xətti olan istənilən nöqtə üçün həm həmin nöqtəni ziyarət edə, həm də tərk edə bilməyəcəyimizi görürük.

Meydanı çəkmək üçün ziyarət etdiyiniz və tərk etdiyiniz ən azı iki nöqtə olmalıdır - bunlar nə başlayacağınız, nə də bitdiyiniz nöqtələrdir. Lakin əslində dörd nöqtə olduğundan heç birinə girə və çıxa bilməyəcəksiniz. biz bir kvadratı bir dəfədən çox geri çəkmədən, diaqonallarla kvadrat çəkə bilməyəcəyimizi görürük.


cavab 2:

Digər cavablar kimi, bu problem də Euler Circuit ilə əlaqədardır.

Euler Path / Circuit-in əsas prinsipləri bunlardır:

Hər bir qovşaqda cüt və ya tək miqdarda keçid ola bilər. Bu qovşaqları ikili edir. Şəbəkənin quruluşu Euler Path / Circuit üçün imkanları qəti şəkildə məhdudlaşdırır, çünki hər iki növ də quruluşu açıq şəkildə məhdudlaşdırır.

Düyünlər belə tələb edir ki, birində başlasanız, eyni ilə bitirməlisiniz. Birində başlamırsansa, eyni ilə bitirmək olmaz.

Tək yol düyünləri birində başlasanız, eyni ilə bitməməyinizi tələb edir. Birində başlamazsan, orada bitirməlisən.

Bu faktların həqiqətən tələb olduğunu təsdiqləmək üçün bir an ayırın.

Bunlardan mümkün Euler Yolu / Dövrə quruluşlarının müəyyən tələblərə sahib olduğu ortaya çıxır:

Devre halda: Quruluş yalnız cüt qovşaqlardan ibarət ola bilər. Sonra A qovşağında başlasanız, yolları keçməlisiniz və nəhayət Euler Circuit-ə aparan A-ya qayıtmaq üçün son yoldan istifadə etməlisiniz. Əlbəttə ki, bu keçid ehtimalı şəbəkənin özünün quruluşundan da asılıdır, ola bilər və ya olmaya da bilər. Ancaq ən azı quruluş bir ehtimal halına gəlməyə imkan verir. Bunun səbəbi budur ki, bütün qovşaqlar tələblərini yerinə yetirə bilər: başlanğıc düyünü orada bitirməyinizi, başlanğıc olmayan düyünlər isə bitməməyinizi tələb edir.

Yol vəziyyəti: iki tək düyündən və n> = 0 olduğu n düyündən ibarət ola bilər, əgər tək olanlardan birində başlayıb digərində qalsanız, onu Euler Yolu halına gətirin. Bir daha, quruluşa görə bu ola bilər ya da ola bilməz, amma ən azından bu mümkün deyil. Bunun səbəbi, başladığımız düyünün (qəribə) sizin orada bitməməyinizi, digər qəribə tərəfin də orada bitməyinizi tələb etməsidir. Hamısı (əgər varsa) bununla bitməməyinizi tələb edir. Beləliklə, bütün bu tələbləri nəzəri olaraq yerinə yetirməkdə problemimiz yoxdur.

Şəbəkələrin bütün digər formaları münaqişələrə səbəb olur. İkidən çox tək düyününüz varsa, iki və ya daha çox düyünün orada bitməyinizi tələb etdiyi bir vəziyyətə girəcəksiniz, bu da qeyri-mümkündür. Yalnız bir tək düyününüz varsa, cüt düyünlərin tələb etməsi vəziyyətində qalırsınız, ancaq tək düyünün də bununla bitməməyinizi tələb edir, ya da əksinə, düyünlər də başlamağınızı tələb edir və bunlarla bitir, ancaq sonra tək düyün də bununla bitməyinizi tələb edir. Tək düyünləriniz varsa, ancaq birində başlasanız problemə gətirib çıxarır, çünki tək düyünlər onlarda bitməyinizi tələb edir, lakin başlanğıc cüt düyün də bunu tələb edir.

Sizin nümunənizdə dörd qovşaq hamısı tək düyündür (hər birində üç keçid var). Beləliklə vəziyyətin qeyri-mümkün olduğu aydındır, çünki hansı qovşaqda başlasanız, digər qovşaqlar hamınızda bitməyinizi tələb edir.


cavab 3:

Fərziyyə: eyni sətir üzərində dəfələrlə çəkilməyə də icazə verilmir, əks halda bunu etmək olardı.

Riyaziyyatda bunları ehtiva edən daha böyük bir problem sinfi bir varlığını soruşur

Eulerian yolu

müəyyən bir qrafikdə.

Qrafikin yalnız hamısı və ya iki ucundan başqa hamısı bərabər dərəcəyə sahib olduğu təqdirdə bir Eulerian yolu ola biləcəyi * məlumdur.

Bu sualdakı qrafik

K_4

, 3 dərəcə 4 zirvəsi ilə, bununla da bir Eulerian yolu yoxdur. Tək bir xəttlə çəkilə bilməz.

Ətraflı məlumat

*: Bunun niyə doğru olduğunu görmək üçün hər dəfə yolun bir təpədən keçdiyində, təpəyə bağlı kənarlardan ikisini istifadə etdiyinə diqqət yetirin. Bu səbəbdən, yolda ilk və sonuncular xaricindəki bütün təpələrin bərabər dərəcəyə sahib olması lazımdır. Bir döngə vəziyyətində, birinci və son təpə eynidir, buna görə bütün zirvələrin bərabər dərəcəsi olmalıdır.


cavab 4:

Bəli var! Bu problem, Euler tərəfindən həll edilən Königsberg körpüsü probleminə bənzəyir.

Görüntüdəki bu yönləndirilməmiş qrafiki nəzərə alsaq, bir evler dövrəsinin mövcud olması üçün lazımlı və kifayət qədər şərtlər bunlardır:

- hər bir təpənin bərabər dərəcəsi olmalıdır - qrafik birləşdirilməlidir

Bir qrafada bir eulerian dövrü varsa, bu dövrə bütün kənarları tam bir dəfə və eyni təpədə başlayaraq bitən bütün təpələri əhatə edir.

Qrafikdə bir eulerian dövrə olması, qrafın əlinizi qaldırmadan çəkilə biləcəyinizə bərabərdir. Çünki belə bir vəziyyətdə ən azı bir yol mövcud olardı, hər bir təpəyə hər bir kənardan yalnız bir dəfə istifadə etmək olar.

Yuxarıdakı şəkildə, dərəcəsi tək olacağı üçün ən azı bir təpə var (bu vəziyyətdə 3). Beləliklə, bir eulerian dövrü mövcud ola bilməz, yəni rəqəmin əlinizi ən azı bir dəfə qaldırmadan çəkiləcəyini nəzərdə tutur.

Riyaziyyat mübadiləsində bu cavabı yoxlayın

http://math.stackexchange.com/questions/292909/proof-cannot-draw-this-figure-without-lifting-the-pen

cavab 5:

tərif: bir təpədə birləşən kənarların sayına dərəcə deyilir.

teorem: qələmi kağızdan qaldırmadan bir qrafiq çəkmək istəyirsənsə, tək dərəcə olan təpələrin sayı ən çox 2 olmalıdır.

qrafikinə bax. diaqonalları olan bir kvadratın hər biri 3-cü dərəcəyə sahib olan 4 təpəsi var, yəni tək dərəcə olan təpələrin sayı 4-dir, yəni 2-dən çoxdur.

qraf nəzəriyyəsində tək dərəcə təpələrin sayı yalnız 0 və ya 2 olmalıdır, onda bu qrafamı qələmi kağızdan qaldırmadan çəkə bilərsiniz və bir tək dərəcə təpədən başlayıb 2 tək dərəcə olarsa digərində bitməlidir. zirvələr.


cavab 6:

Tərif: Tək kənarları birləşdirən şaquli tək şaquli, cüt kənarları olan şaquli cüt şaquli adlanır. Meydanın dörd təpəsini EG, hər biri 3 kənara birləşdirir, buna görə hamısı tək təpələrdir. Teorem1: Qrafik cüt "tək təpələr" (və ya 0/2/4/6 ..., 1/3/5/7 ... tək təpələri ehtiva edən bir qrafik yoxdur.) Teorem2: 0/2 ilə bir qrafik tək təpələr bir qaçışda çəkilə bilər, digərləri edə bilməz (Euler). Qrafanızda 4 tək təpə var, buna görə də bir dəfədə çəkilə bilməz: başqa sözlə, qələminizi kağızdan bitirmək üçün kağızdan buraxmalısınız.


cavab 7:

Çox sadə bir şəkildə, yolun yalnız iki ucu ola bilər və sonu başlanğıcla eyni nöqtə olmadıqca, tək sayda seqmentlə kəsişən nöqtələrdə olacaqlar. Diaqonalları olan bir kvadrat, onu kəsən 3 seqmentli 4 qovşaq olduğundan, ən azı iki yoldan düzəldilməlidir.