• LF몰 이벤트
  • 파일시티 이벤트
  • 캠퍼스북
  • 서울좀비 이벤트
  • 탑툰 이벤트
  • 닥터피엘 이벤트
  • 아이템베이 이벤트
  • 아이템매니아 이벤트

[그래프의응용] 그래프의 응용

*일*
개인인증판매자스토어
최초 등록일
2003.09.18
최종 저작일
2003.09
2페이지/한글파일 한컴오피스
가격 1,000원 할인쿠폰받기
다운로드
장바구니

목차

없음

본문내용

최소경비 신장트리(MST)
그래프의 모든 노드를 연결하고 그 가중치의 합이 최소인 신장트리
<정의>: 최소경비 신장트리
가중치 그래프 G=(V, E, W)에서 경로 P=(v0, v1,..., vn)가 있는 서브 그래프의 가중치의 합
가 최소인 비싸이클 그래프를 최소경비 신장트리(MST)라 한다.
Kruskal 알고리즘
T: n 노드로 구성된 노드의 집합으로 초기에는 empty
E: 에지의 집합으로 초기에는 모든 에지를 포함
while (edge_nr(T)<n-1 and E≠ε) do
- E로부터 가중치가 최소인 에지 (v, w)∈E를 택한다.
- E=E - {v, w)
- 그리고 (v, w)가 T에서 싸이클을 이루지 않으면 T=T∪{w}
od
if (T가 n-1에지 보다 적은 에지를 갖으면)
then
printf("no spanning tree");
Prim 알고리즘
1) 그래프에서 임의의 출발 노드 x를 정한다. 그리고 다음과 같이 초기화한다.
V1={x}; // 신장트리를 구성하는 노드집합
V2={0}; // V1에 속한 노드들에 인접해 있는 후보노드 집합
V3=V-{V1}; // 아직 신장트리와 무관한 노드의 집합
E1={0}; // 신장트리를 구성하는 에지집합
E2={0}; // (V1, V2)의 관계에 놓인 후보에지로서 같은 노드에 두개의
에지가 있을 경우에는 최소 가중치를 갖는 에지로 구성.

2) while (V1≠V) do // 그래프의 모든 노드가 신장트리를 구성할 때까지
2.1) 정해진 노드로부터 신장트리를 구성할 수 있는 후보에지와 노드를 결정
2.1.1) for (x∈V1 and y∈V2: ∃(x, y)) do // 중첩 후보에지 결정
if (모든 x∈V1에 대해서 노드 y에 에지가 여러개 있으면)
- 가중치가 가장 작은 에지만 남겨두고 모든 에지를 후보에지에서 삭제한다.
E2=E2-{e}∪(x, y)
2.1.2) for (x에 인접한 노드 z∈V3에 대하여) do // 후보노드 결정
{ V2=V2∪{z};
V3=V3-{z};
E2=E2∪(x, z);

참고 자료

없음
*일*
판매자 유형Bronze개인인증

주의사항

저작권 자료의 정보 및 내용의 진실성에 대하여 해피캠퍼스는 보증하지 않으며, 해당 정보 및 게시물 저작권과 기타 법적 책임은 자료 등록자에게 있습니다.
자료 및 게시물 내용의 불법적 이용, 무단 전재∙배포는 금지되어 있습니다.
저작권침해, 명예훼손 등 분쟁 요소 발견 시 고객센터의 저작권침해 신고센터를 이용해 주시기 바랍니다.
환불정책

해피캠퍼스는 구매자와 판매자 모두가 만족하는 서비스가 되도록 노력하고 있으며, 아래의 4가지 자료환불 조건을 꼭 확인해주시기 바랍니다.

파일오류 중복자료 저작권 없음 설명과 실제 내용 불일치
파일의 다운로드가 제대로 되지 않거나 파일형식에 맞는 프로그램으로 정상 작동하지 않는 경우 다른 자료와 70% 이상 내용이 일치하는 경우 (중복임을 확인할 수 있는 근거 필요함) 인터넷의 다른 사이트, 연구기관, 학교, 서적 등의 자료를 도용한 경우 자료의 설명과 실제 자료의 내용이 일치하지 않는 경우

이런 노하우도 있어요!더보기

찾던 자료가 아닌가요?아래 자료들 중 찾던 자료가 있는지 확인해보세요

  • 한글파일 자료구조 요약정리 7페이지
    자리가 원소의 값에 의해 결정되는 자료구조 -매우 빠른 응답을 요구하는 응용에 ... [가중치 그래프] -간선에 비용이나 가중치가 할당된 그래프 [부분 그래프] ... 그래프의 특수한 형태로써 사이클을 가지지않는 연결 그래프 [완전 그래프]
  • 한글파일 Web 3.0과 IPFS 13페이지
    보다 명확하게 표현되고, 효율적으로 관리되며, 보안성이 향상되며, 새로운 응용 ... 해시그래프란 무엇인가요? ... 관계를 그래프 형태로 구성하여 분산 원장을 생성합니다.
  • 워드파일 [레포트] 이산수학 Assignment#8 8페이지
    4) 게임 - (2) 트리는 컴퓨터 관련 학문에 있어서 다양한 분야들에 응용될 ... 선택 문제 2) 다음의 그래프 중 트리에 해당하지 않은 것은? ... . - (o) 트리는 연결되어 있고 사이클이 없는 그래프로서 어느 한 연결선만
  • 한글파일 이산확률분포, 연속확률분포 그래프, 기본개념 및 응용사례 13페이지
    1. 이산확률 분포 1)베르누이분포 베르누이 시행 (Bernoulli Trial): 베르누이 시행은 결과가 두 가지 중 하나로만 나오는 실험 또는 시행을 말합니다. 이러한 시행에서 "성공" 또는 "실패"와 같이 두 가지 결과만 가능합니다. 베르누이 확률변수 (Berno..
  • 한글파일 경북대 기초전기전자실험 A+ 스트레인 게이지 9페이지
    그래프 추의 무게와 전압은 선형그래프를 나타내었고 기울기는 추의 무게가 증가하면 ... 응용분야는 로드 셀 및 Torque 측정용 자동차 , 자기 부상 열차, 항공 ... 전압신호를 발생하는 변압기이며, 디지털 인디게이터는 스트레인 게이지를 응용
더보기
최근 본 자료더보기
  • 프레시홍 - 전복
탑툰 이벤트
[그래프의응용] 그래프의 응용
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업