방송대 이산수학 리뷰 / 난이도 및 시험문제

(𝑥+𝑦)⁶ 에서 𝑥⁴ 𝑦² 의 계수는?

1

6

2

12

3

15

 

타일을 직렬로 6장을 붙이려고 한다. 준비된 타일은 금색이 1개, 은색이 3개, 검은색이 2개이다. 타일을 붙이는 방법은 모두 몇 가지인가?

1

10

2

30

3

60

4

64

1 * 1 = 1

1 * 0 = 0

0 * 1 = 0

0 * 0 = 0

쌍조건 명제와 Exclusive OR는 서로 반대의 진리값을 갇는다.

R1

R2 = R1 부울곱 R1

R3 = R1  부울곱 R2

r1, r2, r3 가 모두 r1에 속하면 추이적이다.

exist => y가 최소한 하나 관계를 맫고 있다(모든 x랑) 

전사함수 = onto function

y의 전체를 사용하면서 y가 겹치지 않을때 전단사 함수

1번 전사함수 아님 (y가 모두 쓰여야 함)

1번 단사함수(다른 x가 다른 y랑 관계)

2번 전사함수

2번 단사 아님

3번 전단사 함수 

( 모든 y와 전사함수)

( 서로 다른 y 단사함수)

전단사함수일때, 역함수 존재함

<10강>

* k5 완전그래프 - 어떤 두개의 꼭지점을 선택해도 서로 연결되어 있음 --> 평면 그래프 아님

* 서로 이분 되어 있고, 서로 이분되어 있는 임의의 두 점을 선택해도 서로 연결됨  

위의 그림에서 k4완전그래프는 3정규그래프 이다.

위의 3 정규그래프는 K4완전그래프이다.

평면 그래프 만드는 법 --> k5완전그래프에서 한 변을 제거하고, 나머지 변이 겹치지 않게 밖으로 연결하면 선이 겹치지 않는 평면 그래프가 된다.

오일러의 공식 - 

위의 그림에서 간선이 겹치지 않고 그릴수 없는 것은 3번이다.(아래참조)

다음 중 그래프에 관련된 서술 중 옳지 않은 것은?

1

그래프의 모든 변들을 각각 한 번씩만 지나는 트레일을 오일러 트레일이라고 한다.

2

그래프의 모든 꼭지점들을 각각 한 번씩만 지나는 트레일을 오일러 투어라고 한다.

3

그래프가 오일러 투어를 가지는 경우 모든 꼭지점의 차수는 짝수이다.

4

모든 꼭지점의 차수가 짝수인 연결그래프는 오일러 투어를 가진다.

정답입니다.

정답 : 2

어떤 연결된 평면 그래프가 꼭지점이 5개, 변이 6개가 있을 때 면의 수는 몇 개인가?

1

3개

2

4개

3

5개

4

6개

정답입니다.

정답 : 1

V−E+F=2 $5-6+�=2$ $�=2+6-5$ $�=3$

오일러 투어에 대한 설명으로 옳은 것은?

1

주어진 그래프가 오일러 투어를 가진다면, 해당 그래프의 모든 꼭지점의 차수는 홀수이다.

2

모든 변을 정확히 한 번씩만 지나가고, 시작점과 종점이 동일하면 오일러 투어라 한다.

3

주어진 그래프가 연결 그래프이고 모든 꼭지점의 차수가 홀수라면, 해당 그래프는 오일러 투어를 가진다.

4

오일러 트레일은 오일러 투어이지만, 오일러 투어라고 해서 반드시 오일러 트레일이 되는 것은 아니다.

정답입니다.

정답 : 2

해밀턴 사이클(Hamiltonian cycle)은 그래프 상의 모든 정점을 한 번씩만 거치고 출발점으로 돌아오는 순환 경로

다음 그래프의 해밀턴 사이클로 틀린 것은?

1

abcda

2

bdcab

3

cbdac

4

dabad

정답 : 4