Главная страница
Навигация по странице:

  • Задача «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли

  • Теорема Дирака.

  • Гамильтоновы графы. Эйлеровы графы. Гамильтоновы графы


    Скачать 0.53 Mb.
    НазваниеЭйлеровы графы. Гамильтоновы графы
    Дата15.06.2020
    Размер0.53 Mb.
    Формат файлаppt
    Имя файлаГамильтоновы графы.ppt
    ТипДокументы
    #130338

    Эйлеровы графы. Гамильтоновы графы


    1


    2


    3


    4


    5


    6


    7


    8


    G


    1


    2


    3


    4


    5


    G


    1


    2


    3


    4


    5


    Уи́льям Ро́уэн Га́мильтон –
    (4 августа 1805 — 2 сентября 1865) — выдающийся ирландский математик, механик и физик .


    Задача «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли


    Достаточные условия гамильтоновости графа


    Теорема Дирака. Пусть  G - неориентированный граф порядка n и
     m - минимальная степень его вершин. Если n≥3  и m ≥n/2, то  G - гамильтонов граф.


    Теорема Оре. Пусть  G - неориентированный граф порядка n. Если  n≥3  и  deg(u)+deg(v) ≥ n для любых двух различных несмежных вершин u  и v , то G - гамильтонов граф.


    Если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины u со степенью u < 2. 


    Необходимое условие гамильтоновости графа

    Задание


    Построить эйлеров, квазиэйлеров, гамильтонов, квазигамильтонов графы порядка n=F+N, p>n, где F-количество букв в Вашей фамилии, N-количество букв в Вашем полном имени. Описать полученные графы матрицами смежности вершин, смежности ребер, инцидентности, Кирхгофа соответственно.



    написать администратору сайта