игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Графы и их применение / Тест 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}files 

 (2) пусть Е - непустое конечное множество , а ϕ=(S1,...,Sm) и τ=(T1,...,Tm) - два семейства его непустых подмножеств. Тогда ϕ и τ имеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества {1,...,m}files 

 (3) пусть Е - непустое конечное множество , а ϕ=(S1,...,Sm) и τ=(T1,...,Tm) - два семейства его непустых подмножеств. Тогда ϕ и τ имеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества {1,...,m}files 

 (4) пусть Е - непустое конечное множество , а ϕ=(S1,...,Sm) и τ=(T1,...,Tm) - два семейства его непустых подмножеств. Тогда ϕ и τ имеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества {1,...,m}files 

Номер 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 и Е 



Главная / Алгоритмы и дискретные структуры / Графы и их применение / Тест 16