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

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

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

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

이름: ____________________   날짜: ____________

1.쉬움

5-정규그래프의 정점이 10개이다(모든 정점의 차수는 5). 간선은 몇 개(|E|)인가?

n = 10k = 5
|E| =
2.쉬움

단순 그래프에 정점이 7개 있고 차수는 4, 2, 2, 2, 2, 1, 1이다. 간선은 몇 개(|E|)인가?

deg: 4, 2, 2, 2, 2, 1, 1
|E| =
3.보통
ABCDEFG오일러 회로오일러 경로, 회로 없음둘 다 아님

연결 그래프에 오일러 회로가 있는가, 회로가 아닌 오일러 경로가 있는가, 둘 다 없는가? 답을 클릭하세요.

|V| = 7|E| = 10
  1. 1오일러 회로
  2. 2오일러 경로, 회로 없음
  3. 3둘 다 아님
4.보통

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

|V| = 15|E| = 24
k =
5.어려움
2111218913153191610ABCDEFG

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

k = 2
  1. 1간선 AB
  2. 2간선 AC
  3. 3간선 BC
  4. 4간선 BD
  5. 5간선 CE
  6. 6간선 DE
  7. 7간선 DF
  8. 8간선 EF
  9. 9간선 GB
  10. 10간선 GD
  11. 11간선 GE
6.어려움
311131491219ABCDEF

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

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

정답표

  1. 1. |E| = 25
  2. 2. |E| = 7
  3. 3. 둘 다 아님
  4. 4. k = 10
  5. 5. 간선 EF
  6. 6. F

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