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

Графы и их применение - тест 13

Упражнение 1:
Номер 1
Пусть граф  имеет n вершин. Когда граф  T является деревом?

Ответ:

 (1) граф T является деревом, если он не содержит циклов и имеет n-1 ребер 

 (2) граф T является деревом, если он связан и имеет n-1 ребер 

 (3) граф T является деревом, если он связан и каждое его дерево является мостом 

 (4) граф T является деревом, если вершины его соединены ровно одной цепью 


Номер 2
Как из связного графа   получить остовное дерево?

Ответ:

 (1) известно, что в связном графе G удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру к одному из оставшихся циклов, и так до тех пор, пока не останется ни одного цикла. В результате получим дерево, связывающие все вершины графа, оно называется остовным деревом 

 (2) в связном графе G удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины графа, оно называется остовным деревом 

 (3) чтобы получить из графа G остовное дерево, нужно удалить все мосты 

 (4) чтобы получить из графа G остовное дерево, нужно соединить все его компоненты мостами 


Номер 3
Как из связного графа получить каркас?

Ответ:

 (1) известно, что в связном графе G удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру к одному из оставшихся циклов, и так до тех пор, пока не останется ни одного цикла. В результате получим дерево, связывающее все вершины графа, оно называется каркасом 

 (2) в связном графе G удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины графа, оно называется каркасом 

 (3) чтобы получить из графа G каркас, нужно удалить все мосты 

 (4) чтобы получить из графа G каркас, нужно соединить все его компоненты мостами 


Упражнение 2:
Номер 1
Граф G состоит из k  компонент. Что нужно сделать, чтобы из заданного графа получить остовной лес?

Ответ:

 (1) чтобы из такого графа получить остовной лес, нужно к каждой компоненте графа применить такую процедуру: в каждой компоненте графа удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшейся компоненты . Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины компоненты, оно называется остовным деревом. А так как у нас было k компонент, то получим остовной лес, состоящий из k остовных деревьев 

 (2) чтобы из такого графа получить остовной лес, нужно к каждой компоненте графа применить такую процедуру: в каждой компоненте графа удалить все циклы, не нарушая связности оставшейся компоненты. Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины компоненты, оно называется остовным деревом. А так как у нас было k компонент, то получим остовной лес, состоящий из k остовных деревьев 

 (3) чтобы из такого графа получить остовной лес, нужно к каждой компоненте графа применить такую процедуру: нужно получить из каждой компоненты графа G остовное дерево, удаляя все мосты в каждой компоненте графа. В результате получим дерево, связывающие все вершины компоненты, оно называется остовным деревом. А так как у нас было k компонент, то получим остовной лес, состоящий из k остовных деревьев 

 (4) чтобы из такого графа получить остовной лес, нужно к каждой компоненте графа применить такую процедуру: получить из каждой компоненты графа G остовное дерево, соединив все его компоненты мостами. В результате получим дерево, связывающее все вершины компоненты, оно называется остовным деревом. А так как у нас было k компонент, то получим остовной лес, состоящий из k остовных деревьев 


Номер 2
Что называется циклическим рангом?

Ответ:

 (1) число удаленных ребер при получении остовного дерева называется циклическим рангом 

 (2) число присоединенных ребер при получении остовного дерева называется циклическим рангом 

 (3) число присоединенных мостов при получении остовного дерева называется циклическим рангом 

 (4) число удаленных петель при получении остовного дерева называется циклическим рангом 


Номер 3
Что называется цикломатическим числом?

Ответ:

 (1) число удаленных ребер при получении остовного дерева  

 (2) циклический ранг 

 (3) число присоединенных ребер при получении остовного дерева  

 (4) число удаленных петель при получении остовного дерева 


Упражнение 3:
Номер 1
Пусть ген G  наследуется и от отца, и от матери с вероятностью  p, а ген  g - с вероятностью q. Чему равна вероятность унаследованных генов?

Ответ:

 (1) p+q=1 

 (2) p-q=1 

 (3) p-q=0 

 (4) p*q=1 


Номер 2
Какой граф описывает ситуацию случая кровного родства ?

Ответ:

 (1) граф является деревом 

 (2) граф не является деревом, так как его вершины слипаются 

 (3) граф является остовом 

 (4) граф является каркасом 




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