무브

오르비

아톰

내 태그

내 태그 설정

입시
학습
생활
클럽
직업·취업
Epioptimus
Centurion

전과반수생 [347366] · MS 2010 · 쪽지

2011-07-09 19:45:37
조회수 412

행렬과 그래프 질문이요!

게시글 주소: https://iu.orbi.kr/0001379441

행렬과 그래프 중 인접행렬이 될 수 있는 조건이
그래프에 있는 꼭짓점에 붙어 있는 변의 수가 같으면 인접행렬이 될 수 있나요?

0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

전과반수생 [347366]

쪽지 보내기

  • Never.stoP · 287359 · 11/07/09 21:00 · MS 2009

    질문을 좀 더 명확히 해주세요. ''꼭짓점에 붙어있는 변의 수가 같으면'' 이 무엇과 같음을 뜻하는지 모르겠네요

    좋아요 0 답글 달기 신고
  • 전과반수생 · 347366 · 11/07/09 21:26 · MS 2010

    각 꼭짓점에 붙어있는 변의 숫자가 모두 같거나 비교해야 되는 그림에서의 각각의 꼭짓점에 있는 변의 수와 똑같다는 것이요!

    좋아요 0 답글 달기 신고
  • Never.stoP · 287359 · 11/07/09 22:57 · MS 2009

    ''꼭짓점에 붙어있는 변의 숫자''를 ''차수''라고 합니다.

    음 그래프에서 각 꼭짓점 마다의 차수 ( 예를 들어 꼭짓점이 5개라면 3, 3, 2, 2, 2 같은 것? ) 와
    인접행렬에서 알 수 있는 차수를 비교했을 때 모두 같다면 이 인접행렬과 그래프가 같다고 볼 수 있냐는 것이죠?

    그렇지 않습니다.

    차수가 3, 3, 2, 2, 2 인 그래프와 그 인접행렬을 생각해봅시다.
    제가 여기에 그림을 못그리는 관계로ㅜ 두 개의 인접행렬을 드릴테니 그려주세요 ㅎㅎ
    X= 0 1 0 1 0 Y= 0 1 0 1 0
    1 0 1 0 1 1 0 1 1 0
    0 1 0 1 0 0 1 0 0 1
    1 0 1 0 1 1 1 0 0 1
    0 1 0 1 0 0 0 1 1 0

    자 그리셨나요??

    두 행렬X와 Y가 나타내는 그래프는 차수가 3, 3, 2, 2, 2 라는 점에서 똑같죠.
    이 때 그래프X와 행렬Y를 비교해 봅시다.
    둘의 차수 구성은 똑같은데 행렬Y는 그래프X의 인접행렬이 되지 못합니다.
    왜냐하면 그래프X에서는 차수가 3인 두 점이 연결되어 있지 않은데,
    그래프Y에서는 차수가 3인 두 점이 연결되어 있기 때문입니다.

    그러므로 차수 비교만으로 두 그래프가 같은지, 혹은 어떤 행렬이 그 그래프의 인접행렬이 될 수 있는지는
    '''''''''''''직접'''''''''''''''' 해보셔야 압니다. ㅜ

    좋아요 0 답글 달기 신고
글쓰기
오르비 1354792번째 회원 가입
ddna
1,422,072 건의 게시물이
블록체인에 디지털 공증되었습니다.
901,751
497,321
22,267
574
159

오늘의 추천 글

2026 수능D - 355

오르비 플레이

오르비 RARE

오르비 과외시장
Move
our corporate site
Orbi Class
on-line classes
Atom
educational books & resources
Gae9
humor and fun

© 2000-2024 Move Inc.

orbisoptimus (v17-7e2515)