Главная / Алгоритмы и дискретные структуры /
Графы и их применение / Тест 16
Графы и их применение - тест 16
Упражнение 1:
Номер 1
Если Е
- непустое конечное множество и ϕ=(S1,...,Sm)
- семейство непустых его подмножеств, то что называется трансверсалью для ϕ
?
Ответ:
 (1) если Е
- непустое конечное множество и ϕ=(S1,...,Sm)
- семейство непустых его подмножеств, трансверсалью для ϕ
называется подмножество множества Е
, состоящее из m
элементов: по одному из каждого множества Si
 
 (2) если Е
- непустое конечное множество и ϕ=(S1,...,Sm)
- семейство обязательно различных непустых его подмножеств, трансверсалью для ϕ
называется подмножество множества Е
, состоящее из m
элементов: по одному из каждого множества Si
 
 (3) если Е
- непустое конечное множество и ϕ=(S1,...,Sm)
- семейство не обязательно пустых его подмножеств, трансверсалью для ϕ
называется подмножество множества Е
, состоящее из m
элементов: по одному из каждого множества Si
 
 (4) если Е
- непустое конечное множество и ϕ=(S1,...,Sm)
- семейство обязательно пустых его подмножеств, трансверсалью для ϕ
называется подмножество множества Е
, состоящее из m
элементов: по одному из каждого множества Si
 
Номер 3
Что называется частичной трансверсалью для ϕ
?
Ответ:
 (1) трансверсаль произвольного подсемейства семейства ϕ
будем называть частичной трансверсалью для ϕ
 
 (2) трансверсаль произвольного подсемейства семейства Е
будем называть частичной трансверсалью для ϕ
 
 (3) трансверсаль произвольного подсемейства семейства ϕ∩E
будем называть частичной трансверсалью для ϕ
 
 (4) трансверсаль произвольного подсемейства семейства ϕ∪E
будем называть частичной трансверсалью для ϕ
 
Упражнение 2:
Номер 2
Что называется матрицей инциденций?
Ответ:
 (1) другой подход к изучению трансверсалей семейства ϕ=(S1,...,Sm)
непустых подмножеств множества E={e1,...,en}
состоит в исследовании (m×n)
- матрицы A=((aij)
, в которой aij=1
если ej∈Si
и aij=0
в противном случае. Любую такую матрицу, все элементы которой равны 0 или 1, называют матрицей инциденций этого семейства 
 (2) другой подход к изучению трансверсалей семейства ϕ=(S1,...,Sm)
пустых подмножеств множества E={e1,...,en}
состоит в исследовании (m×n)
- матрицы A=((aij)
, в которой aij=1
если ej∈Si
и aij=0
в противном случае. (Любую такую матрицу, все элементы которой равны 0 или 1, называют матрицей инциденций этого семейства) 
 (3) другой подход к изучению трансверсалей семейства ϕ=(S1,...,Sm)
непустых подмножеств множества E={e1,...,en}
состоит в исследовании (m×m)
- матрицы A=((aij)
, в которой aij=1
если ej∈Si
и aij=0
в противном случае. Любую такую матрицу, все элементы которой равны 0 или 1, называют матрицей инциденций этого семейства 
 (4) другой подход к изучению трансверсалей семейства ϕ=(S1,...,Sm)
непустых подмножеств множества E={e1,...,en}
состоит в исследовании (n×n)
- матрицы A=((aij)
, в которой aij=1
если ej∈Si
и aij=0
в противном случае. Любую такую матрицу, все элементы которой равны 0 или 1, называют матрицей инциденций этого семейства 
Упражнение 3:
Номер 1
Чему равен словарный ранг матрицы?
Ответ:
 (1) словарный ранг (0,1)-матрицы А равен минимальному числу μ
строк и столбцов, которые в совокупности содержат все единицы из А 
 (2) cловарный ранг (0,1)-матрицы А равен максимальному числу μ
строк и столбцов, которые в совокупности содержат все единицы из А 
 (3) cловарный ранг (0,1)-матрицы А равен минимальному числу μ
строк, которые в совокупности содержат все единицы из А 
 (4) cловарный ранг (0,1)-матрицы А равен минимальному числу μ
столбцов, которые в совокупности содержат все единицы из А 
Номер 2
Когда два семейства непустых подмножеств имеют общую трансверсаль?
Ответ:
 
(1) пусть
Е
- непустое конечное множество , а
ϕ=(S1,...,Sm)
и
τ=(T1,...,Tm)
- два семейства его непустых подмножеств. Тогда
ϕ
и
τ
имеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества
{1,...,m}
 
 
(2) пусть
Е
- непустое конечное множество , а
ϕ=(S1,...,Sm)
и
τ=(T1,...,Tm)
- два семейства его непустых подмножеств. Тогда
ϕ
и
τ
имеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества
{1,...,m}
 
 
(3) пусть
Е
- непустое конечное множество , а
ϕ=(S1,...,Sm)
и
τ=(T1,...,Tm)
- два семейства его непустых подмножеств. Тогда
ϕ
и
τ
имеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества
{1,...,m}
 
 
(4) пусть
Е
- непустое конечное множество , а
ϕ=(S1,...,Sm)
и
τ=(T1,...,Tm)
- два семейства его непустых подмножеств. Тогда
ϕ
и
τ
имеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества
{1,...,m}
 
Номер 3
Предположим, что E={1,2,3,4,5,6}
, а S1=S2={1,2},S3=S4={2,3},S5={1,4,5,6}
Имеет ли семейство а ϕ=(S1,...,S5)
трансверсаль?
Ответ:
 (1) да 
 (2) нет, так как здесь невозможно найти пять различных элементов из Е
- по одному из каждого подмножества Si
 
 (3) да, если заменить Si
 
 (4) да, если заменить Si
и Е