Страница: 2/3
Чтоб показать вам всю сложность нахождения гамильтонова цикла рассмотрим граф из семи точек, приведенный на рисунке ниже. Если попытаться самому придумать гамильтонов цикл то на это уйдет от 30 минут до нескольких часов.
На рисунке показан граф с 7 вершинами; сплошные линии- гамильтонов цикл для данного графа пунктир ребра по которым не прошла кривая гамильтонова цикла.
В качестве Боба и Алисы могут выступать компьютер и пластиковая карточка типа той которая сейчас служит для банковских расчетов. Даже если человек сможет подключится к проверяющему компьютеру то он все равно не сможет узнать гамильтонов цикл для графа находящегося на карточке.
Метод ZKP может использоваться не только для примера с графами но и на многих других примерах, просто в данном случае легче всего объяснить в чем суть метода ZKP. Хоть и явны видны преимущества данного вида кодировки нельзя забывать и про систему (PASSWORD)овых шифровок так как если охраняется не очень важный объект то проще и быстрее проверять (PASSWORD) чем проводить проверку методом ZKP.
Мы попробовали пройти систему кодировки ZKP.
Для примера мы разобрали разные фрагменты графов что бы найти закономерность в построении гамильтонова цикла .Мы можем найти алгоритм построения гамильтонова цикла на данных фрагментах, что бы в дальнейшем строить этот цикл на более сложных графах.
Пример1.
A A E D C B F S N P G A
В данном графе легко можно B построить гамильтонов цикл
F G E так как в данном графе есть два
S P контура , которые находятся
N друг в друге и соединены точками.
C D Таким образом построение данного графа является самим гамильтоновым циклом и практически все графы строятся на основе самого гамильтонова цикла. С добавлением других ребер.
Гамильтонов цикл легко искать если граф имеет вид замкнутых контуров соединенных более чем через две точки друг с другом
Пример 2.
На данном графе намного сложнее построить гамильтонов цикл так как не все точки соединены с друг другом
А Гамильтонов цикл:
Б Л Д Б А Л К В С Е Д
Д Е В данном случае мы нашли
С его за 7 минут 34 секунды
В К и если бы точки Б и В не лежали бы рядом то, это заняло бы у нас намного больше времени. Граф не обязательно должен быть таким , главное что граф может растягиваться как угодно ,и точки могут менять свои координаты, главное что бы A соединялось с
Реферат опубликован: 16/06/2007