Въведение, Хамилтонови графики, Основни дефиниции и резултати, Хамилтонови теореми за достатъчност
Целта на курсовата ми работа е:
1. Запознаване с основните понятия, свързани с хамилтоновите графики и цикли.
2. Разгледайте проблемите и методите за намиране на хамилтонови цикли в графики
3. Създаване на програма за намиране на хамилтонови цикли.
На първо място, за да се изясни и изясни терминологията, бих искал да дам определения на някои елементи на графиката, като маршрут, верига, цикъл.
По маршрут в графиката G(V, E) се нарича редуваща се последователност от върхове и ребра:, ..., в която всеки два съседни елемента са инцидентни. Ако =, тогава маршрутът е затворен, в противен случай е отворен.
Ако всички ръбове са различни, тогава маршрутът се нарича верига. Ако всички върхове (а оттам и ръбовете) са различни, тогава маршрутът се нарича проста верига.
Затворена верига се нарича цикъл; затворена проста верига се нарича прост цикъл. Графика без цикли се нарича ациклична. За диграфите веригата се нарича път, а цикълът се нарича контур.
Основни определения и резултати
Името "хамилтонов цикъл" идва от проблема "Пътуване около света", предложен от ирландския математик Уилям Хамилтън през 1859 година. След напускането на първоначалния връх на графиката беше необходимо да се обиколят всичките й върхове и да се върне към началната точка. Графиката представлява подреждане на додекаедър, на всеки от 20-те върха на графиката е присвоено името на голям град в света.
Ако графиката има прост цикъл, съдържащ едновременно всички върхове на графиката, тогава се нарича такъв цикъл Хамилтонов цикъл, и графиката се извиква Хамилтонова графика. Извиква се графика, която съдържа прост път през всеки от нейните върхове полухамилтонов. Тази дефиниция може да бъде разширена до насочени графики, ако пътят се счита за насочен.
Хамилтоновият цикъл не включва непременно всички ръбове на графиката. Ясно е, че само свързан граф може да бъде хамилтонов и че всеки хамилтонов граф е полухамилтонов. Имайте предвид, че хамилтоновият цикъл не съществува във всяка графика.
Коментирайте.
Всеки брой G може да се превърне в хамилтонов граф чрез добавяне на достатъчен брой върхове. За това например е достатъчно до върховете v1, ..., vp броя G добавяне на върхове u1, ..., нагоре и множеството от ръбове vi, ui)> ui, vi + 1)>.
Степента на връх v е броят на ребрата д(v) инцидент с него и цикълът се брои два пъти. В случай на насочена графика степента направете(v) по изходящите дъги и ди(v) - чрез входящи.