이산구조(이산수학) 레포트 과제 웰치포웰, 슈도코드 등

소개

이산수학 과제 작성한것입니다.
웰치포웰 알고리즘 소스, 연습문제 40번, 슈도코드 정의 문제 입니다~

컴파일 실행환경

없음

본문내용

슈도코드 정의
의사코드(슈도코드, pseudocode)는 특정 프로그래밍 언어의 문법을 따라 씌여진 것이 아니라, 일반적인 언어로 코드를 흉내내어 알고리즘을 써놓은 코드를 말한다. 의사(疑似)코드는 말그대로 흉내만 내는 코드이기 때문에, 실제적인 프로그래밍 언어로 작성된 코드처럼 컴퓨터에서 실행할 수 없으며, 특정 언어로 프로그램을 작성하기 전에 알고리즘의 모델을 대략적으로 모델링하는 데에 쓰인다.

Welch-Powell 알고리즘

1. G정점을 차수에 따라 내림차순으로 배열한다(차수가 같은 정점들 간의 순서는 무시해도 좋다)
2. 차수가 가장 높은 정점을 첫번째 색으로 채색하고, 이 정점과 인접하지 않는 모든 정점을 같은 색으로
채색한다.
3. 채색되지 않은 정점 중 가장 높은 차수를 가지는 정점을 선택하여 두번째 색으로 채색하고,
이 정점과 인접하지 않은 모든 정점을 같은 색으로 채색한다.
4. 모든 정점이 채색될 때까지 다른 색으로 과정(3)을 반복한다.

40. D는 6개의 정점 ʋ1, ʋ2, .... , ʋ6과 8개의 연결선을 가지는 유향그래프이고, B=(bij)는 유향 그래프의 D의 8×2 연결선 행렬 이다. 카드 덱에는 8장의 카드가 있고, 각 카드에는 연결선 행렬의 각 행이 천공되어 있을 때, 다음 프로그램을 작성하고
(1) 각 정점의 진입 차수와 진출 차수를 구하는 프로그램
(2) D의 논리 행렬 M=(mij)을 구하는 프로그램
(3) 각 정점이 source 인지 sink 인지를 결정하는 프로그램
다음 데이터를 이용하여 테스트 하여라.

참고자료

· 없음