Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)



Download 1,82 Mb.
bet6/29
Sana14.07.2022
Hajmi1,82 Mb.
#798900
TuriЛекции
1   2   3   4   5   6   7   8   9   ...   29
Bog'liq
Теория графов

a

b

c

d

a

0

1

1

0

b

1

0

1

0

c

1

1

0

1

d

0

0

1

0




u

v

w

x

a

1

0

0

0

b

1

1

1

0

c

0

1

0

1

d

0

0

1

1

8. Написать для данного графа матрицы смежности и инцидентности, задать его списком ребер и вершин.


  1. Докажите, что полные (пустые) графы изоморфны тогда и только тогда, когда они имеют одинаковое количество вершин.

  2. Найдите все попарно неизоморфные графы пятого порядка.


Лекция 16. Маршруты, пути, цепи, циклы. Эйлеровы циклы и цепи. Гамильтонов цикл. Взвешенные графы (4 ачса)
План:
1. Маршруты и пути, цепь, цикл.
2. Связность. Компоненты связности.
3. Цикл Эйлера. Граф Эйлера. Теоремы о графах Эйлера, гамильтоновый цикл. Гамильтон Граф.
Ключевые слова: маршрут, пути, цепь, цикл, компоненты связности, цикл Эйлера, граф Эйлера, гамильтоновый цикл, граф Гамильтона.


1. Маршруты и пути, цепь, цикл.
Определение. Последовательность
v1x1v2x2v3...xkvk+1, (где k1, viV, i=1,...,k+1, xjX, j=1,...,k)
в которой чередуются вершины и ребра (дуги) и для каждого j=1,...,k ребро (дуга) xj имеет вид {vj,vj+1} (для орграфа (vj,vj+1)), называется маршрутом, соединяющим вершины v1 и vk+1 (путем из v1 в vk+1).

Пример


















v1x1v2x2v3x4v4x3v2 - маршрут,


x1x2x4x3 - маршрут можно восстановить и по этой записи,
v1v2v3v4v2 - если кратности ребер (дуг) равны 1, то можно и так.
v2x2v3x4v4 - подмаршрут.
Число ребер в маршруте (дуг в пути) называется длиной маршрута (пути).
Маршрут (путь) называется замкнутым, если начальная вершина совпадает с конечной v1=vk+1.
Незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны называется цепью.
Цепь, в которой все вершины попарно различны называется простой цепью.
Замкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется циклом (контуром).
Цикл (контур), в котором все вершины попарно различны называется простым.
Теорема. В псевдографе G (в ориентированном псевдографе D) из всякого цикла (контура) можно выделить простой цикл (простой контур).
Доказательство (индукцией).
Пусть k – количество ребер, k+1 – количество вершин в цикле (или контуре).
При k=1 (петля) цикл всегда является простым.
Пусть утверждение верно для цикла длиной k-1. Допустим, в цикле имеются совпадающие вершины: vi=vj, (если их нет, то цикл - простой). Тогда удалим из цикла часть, заключенную между viи vj (вместе с vj). Получившийся цикл имеет меньшую длину и в силу индуктивного предположения из него можно выделить простой цикл.

Теорема. Из всякого незамкнутого маршрута (пути) можно выделить простую цепь с теми же начальной и конечной вершинами.
Доказательство || аналогично предыдущему.
Определение. Композицией путей (маршрутов)
1=v1x1v2...xk-1vk, 2=vkxkvk+1...xL-1vL называется путь (маршрут) 1 2=v1x1v2...xk-1vkxkvk+1xk+1...xL-1vL.



Download 1,82 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   ...   29




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish