| English | 의미 |
|---|---|
| graph/ɡræf/ | 그래프 |
| vertices/ˈvɜːtɪsiːz/ | 정점 |
| edges/ˈedʒɪz/ | 변 |
| degree/dɪˈɡriː/ | 차수 |
| path/pæθ/ | 경로 |
| cycle/ˈsaɪkl/ | 사이클 |
| connected/kəˈnektɪd/ | 연결된 |
| tree/triː/ | 나무 |
| weighted graph/ˈweɪtɪd ɡræf/ | 가중 그래프 |
| shortest path/ˈʃɔːtɪst pæθ/ | 최단 경로 |
연결 모델은 가정이 필요합니다
- 그래프(graph) 는 정점(vertices) 와 변(edges) 을 가집니다. 이들이何を代表하는지 결정하고 연결이 방향성(directed), 가중치(weighted) 또는 무방향(undirected)인지 결정하십시오.
- 이 워크시트는 루프나 중복 변이 없는 유한 단순 무방향 그래프를 사용합니다. 그리기 위치는 연결을 변경하지 않지만, 화살표나 변 가중치는 수학적 모델을 변경할 수 있습니다.
연결을 일관되게 세기
- 차수(degree) 는 단순 무방향 그래프에서 연결된 변의 개수를 세는 것입니다. 총 차수는 변의 개수의 두 배이므로 반드시 짝수여야 합니다.
- 경로(path) 는 연결을 따르는 것이며, 사이클(cycle) 은 다른 정점을 반복하지 않고 시작점으로 돌아오는 것입니다. 그래프가 연결된(connected) 것은 각 정점이 모든 다른 정점에서 도달 가능할 때입니다.
루프가 없는 단순 무향 그래프에서 한 정점에 네 개의 엣지가 연결되어 있습니다. 이 정점의 차수(degree)는 무엇입니까?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
해당 그래프 규약 하에 인시던트 엣지의 개수인 4가 바로 차수입니다.
트리는 두 가지 속성을 가져야 합니다
- 트리(tree) 는 연결되어 있고 사이클이 없습니다. n개의 정점을 가진 유한 트리는 n-1개의 변을 가집니다.
- 변이 n-1개라는 것만으로는 트리를 증명할 수 없습니다: 삼각형과 별개의 2-정점 구성 요소가 결합된 경우 5개의 정점과 4개의 변을 가지지만 연결되지 않았고 사이클이 있습니다.
나무 그래프에 정점이 4개 있습니다. 변은 몇 개인가?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
정점이 4개인 유한 트리는 n − 1 = 3개의 엣지를 가집니다. 이 개수는 그래프가 실제로 연결되어 있고 사이클이 없음에 의존합니다.
모든 정점을 연결하는 최소 비용 연결 하위 그래프가 왜 사이클을 포함하지 않는가? (단, 간선 비용은 양수임)
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
어떤 사이클 간선을 제거해도 연결성은 유지되며 총 비용이 감소한다(간선 가중치가 양수이기 때문). 따라서 이러한 조건 하에서 사이클이 있는 하위 그래프는 최소일 수 없다.
양수 비용의 연결 도로. 엄격히 양의 도로 비용을 가진 연결 네트워크에서 사이클 변을 제거하면 연결성이 유지되고 비용이 감소합니다. 따라서 최소 비용 연결 부분 그래프는 트리입니다. 최소 신장 트리(minimum spanning tree)를 찾으려면 사이클 없이 모든 정점을 연결하는 변을 선택하십시오; 가장 저렴한 n-1개의 변을 무분별하게 선택하면 별개의 구성 요소가 남을 수 있습니다.
최단 경로는 신장 트리가 아닙니다
- 가중 그래프(weighted graph) 는 각 변에 지정된 값을 부착합니다. 최단 경로(shortest path) 는 주어진 양 끝점 간 경로의 무게를 최소화합니다.
- 최소 신장 트리는 대신 모든 정점을 최소 총 포함 무게로 연결합니다. 최단 경로는 직접적인 비싼 경로보다 많은 변을 가질 수 있으므로 변의 개수가 아닌 무게를 합산하십시오.
각 상황을 정점과 변이 되어야 할内容与 매칭하십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
정점이 무엇을 나타내는지 결정하는 것이 모델링 단계이며, 여기서 점수를 받습니다.
닫힌 가장자리가 타당성을 변경합니다. Sheet 4.5는 무게 7의 경로를 찾아낸 후, 닫힌 가장자리를 확인하고 무게 9인 대체안을 점검합니다. 더 이상 존재하지 않는 경로에 대해 기존 총합을 재사용하지 마십시오.
서로 다른 그림은 반드시 다른 그래프여야 합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
서로 다른 레이아웃이 동일한 라벨링된 인접 행렬을 가질 수 있다. 지정된 그래프에 방향과 가중치가 포함되어 있다면 이를 함께 비교하라.
질문과 관련된 모든 구조를 비교하십시오: 정점 대응, 인접성, 방향 및 명시된 경우 가중치. 비슷해 보이는 그림이 반드시 동일한 그래프를 나타내는 것은 아닙니다. 다른 레이아웃도 동일한 레이블 연결을 나타낼 수 있습니다.