정답이 있는 그래프 이론 학습지

무료 인쇄용 그래프 이론 학습지: 쉬운 문제부터 시험 수준까지 6문제, 정답표 포함. 인쇄하거나 PDF로 저장하세요.

새 학습지힌트와 함께 온라인으로 연습하기

교수자 안내: 수업에서 무료로 인쇄, 복사, 사용할 수 있습니다. 새 워크시트마다 값이 새로 바뀌고 별도의 정답이 함께 제공됩니다. 강의 페이지에 ExamProblems 링크를 걸어 주시면 감사하겠습니다.

이름: ____________________   날짜: ____________

1.쉬움

트리의 간선이 6개이다. 정점은 몇 개(|V|)인가?

|E| = 6
|V| =
2.쉬움
AABBCCDD0110101011010010

단순 무방향 그래프의 인접 행렬이 주어져 있다. 그래프의 간선은 몇 개(|E|)인가?

|E| =
3.보통

연결 그래프의 정점이 16개이고 간선이 16개이다. 신장 트리가 남도록 제거해야 하는 간선은 몇 개(k)인가?

|V| = 16|E| = 16
k =
4.보통

완전그래프 K5의 서로 다른 해밀턴 회로는 몇 개(H)인가? 시작 정점이나 방향만 다른 회로는 같은 것으로 센다.

K5
H =
5.어려움
841532061ABCDE

크루스칼 알고리즘이 최소 신장 트리를 만든다. 4번째로 추가하는 간선을 클릭하세요. 건너뛴 간선은 세지 않는다.

k = 4
  1. 1간선 AB
  2. 2간선 AC
  3. 3간선 BC
  4. 4간선 BD
  5. 5간선 CE
  6. 6간선 DE
  7. 7간선 BE
6.어려움
673224312ABCDEF

다익스트라 알고리즘이 A에서 시작한다. 3단계에서 확정(영구 결정)되는 정점을 클릭하세요. A 자신은 1단계이다.

시작: A단계 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F

정답표

  1. 1. |V| = 7
  2. 2. |E| = 4
  3. 3. k = 1
  4. 4. H = 12
  5. 5. 간선 AB
  6. 6. C

자세한 단계별 풀이: examproblems.com에서 이 주제를 연습하세요.