1. 5개의 정점을 가지고 각 정점의 차수가 3인 그래프가 존재할 수 있음??
각 정점의 차수나 변은 정점의 개수와 같거나 커야하는게 맞음??
2. 4개의 변과 4개의 정점을 가지고 정점마다 각각 1개,2개,3개,4개의 차수를 가진 그래프를 만들 수 있음??
이것도 불가능한거 아닌가..
3. Simple Graph에서 5개의 정점을 가지고 각각 2개,3개,3개,4개,4개의 차수를 가진 그래프를 만들 수 있는지???
좀 이론적인 문제인데 아직 개념이 안잡혀서 도와주세요..
1번은 불가능하지. 모든 정점의 차수가 3이면 그래프 모든 정점의 차수의 합이 15라는 건데, 아마 알겠지만 그래프 내 모든 정점의 차수의 합은 짝수여야 함.
2번은 뭔 소린지 모르겠다 미안
오!! 일찍인데 답변 감사합니다... 저 문제는 제가 해석을 잘못한걸수도 있는데 원문제는
Four edges, four vertices having degrees 1,2,3,4 라는 문제임당..
3번은 결론부터 말하자면 가능함
edge가 4개인데 차수가 1,2,3,4라고? 차수 다 더하면 10인데 edge가 4개면 불가능하지. 넌센스 문제가 아닌 이상에는
오 감사합니다
ㅇㅇ//넌센스->난센스 (국어사전 - 난센스 (nonsense)[명사] 이치에 맞지 아니하거나 평범하지 아니한 말 또는 일.) [리듬 맞춤법 봇♬]