Що таке теорія графів задачі Кенігсберзького мосту?

Проблема Кенігсберзького мосту була стара головоломка щодо можливості знайти шлях через кожний із семи мостів, які перетинають розгалужену річку, що протікає повз острів, але не перетинаючи жоден міст двічі. Ейлер стверджував, що такого шляху не існує. 15 липня 2024 р

Сім Кенігсберзьких мостів — історично видатна задача в математиці. Його негативне вирішення Леонгардом Ейлером у 1736 році заклало основи теорії графів і прообразувало ідею топології..

Однак у Кенігсберзькій проблемі всі вершини мають непарну кількість ребер, приєднаних до них, тому прогулянка через кожен міст неможлива. Доведення Ейлера поклало початок теорії графів.

Цей граф має чотири вершини непарного ступеня, тому неможливо мати ейлерів шлях або шлях, де кожне ребро використовується один раз і тільки один раз. Використовуючи це міркування, Ейлер сказав, що через Кенігсберзькі мости немає абсолютно жодного шляху.

Проблема Кенігсберзького мосту запитує, чи можна всі сім мостів міста Кенігсберг (ліворуч; Kraitchik 1942), який раніше був у Німеччині, але тепер відомий як Калінінград і частина Росії, через річку Прегер проїхати за одну поїздку, не повертаючись назад , з додатковою вимогою, щоб поїздка закінчувалася в …

Згідно з народними переказами, постало питання, чи може громадянин прогулятися містом так, щоб кожен міст проходив рівно один раз. У 1735 році швейцарський математик Леонхард Ейлер представив рішення цієї проблеми, дійшовши висновку, що така прогулянка була неможлива.