Дискретная математика. Громов Ю.Ю - 74 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

74
4. Приведите пример связного неориентированного графа, который
является одновременно:
а) эйлеровым и гамильтоновым;
б) эйлеровым и негамильтоновым;
в) неэйлеровым и гамильтоновым;
г) неэйлеровым и негамильтоновым.
14. ПОКРЫТИЯ И НЕЗАВИСИМЫЕ МНОЖЕСТВА
Независимым множеством вершин графа G называется множество
попарно не смежных вершин неориентированного графа G, порождающее
пустой подграф этого графа. Независимое множество вершин графа G
называется максимальным независимым множеством вершин графа G,
если оно не является собственным подмножеством другого независимого
множества вершин этого графа. Максимальное независимое множество
вершин графа G называется наибольшим независимым множеством вер-
шин графа G, если оно содержит наибольшее количество вершин. Мощ-
ность наибольшего независимого множества вершин графа G будем на-
зывать числом независимости графа G и обозначать α(G).
Для графа G, изображённого на рис. 39, независимыми множествами
вершин являются, например, множества {2, 4}, {2, 4, 7} и {1, 3, 4, 7};
максимальными независимыми множествами вершин − множества {2, 4, 7}
и {1, 3, 4, 7}; наибольшим независимым множеством вершин − множест-
во {1, 3, 4, 7}, а число независимости графа α(G) = 4.
Кликой графа G называется множество его попарно смежных вер-
шин, порождающее полный подграф графа G. Клика графа G называется
максимальной кликой графа G, если она не является собственным под-
а)
a b c
f e d
k m
g
h
p
q
б)
a
b
d
e
f
g
h
k
m
p
q
r
s
t
u
v
w
x
y
c

Страницы