Tip:
Highlight text to annotate it
X
귀중한 경험입니다. 오늘 우리는
탐욕 알고리즘에 대해 이야기할 것입니다.
그러나 우리는 그것을 그래프의 맥락에서 할 것입니다.
저는 그래프에 대해 복습하고 싶습니다,
그것은 여러분 교재의
부록 B에서 볼 수 있는 것입니다.
여러분이 최근에 부록 B를 보지 못했으면, 앉아서 다시 보세요.
그것은 특히 퀴즈에
도움이 될 것입니다.
Digraph가 뭐죠? 무엇의 약칭인가요?
Directed graph(방향 그래프)입니다.
G = (V,E) 입니다.
저는 항상
여러분에게 vertices(정점)에 대해 말하도록 합니다.
단수는 vertices가 아니라
vertex입니다.
복수는 vertices입니다. 단수는 vertex입니다.
그것은 이상한 영어 단어 중 하나입니다.
그것은 아마 프랑스어 등에서 왔을 겁니다.
저는 모릅니다.
우리는 집합 E를 가지고, 그것은 V와 V의 교집합의 부분 집합입니다.
그것이 방향 그래프입니다.
방향이 없는 그래프 E는 정렬 되지 않은 쌍을 포함합니다.
네? 그것은 라틴어 입니다.
아마 매우 오래되었을 거에요.
아마 프랑스어는 아닐겁니다.
그것은 1570년에 사용되기 시작했습니다.
좋아요,
그래서 엣지의 수(|E|)는, 그것이 방향이 있든 없든,
무엇의 O입니까? V^2, 좋아요.
우리가 그래프를 다룰 때,
우리는 많은 집합을 다룹니다.
우리는 일반적으로 O 안에 '| |' 개념을 넣습니다.
그것은 적용되기 때문입니다. 그것은 더 엉망으로 만듭니다.
다시 한번, 개념의 또 다른 남용이 있습니다.
그것은 O(V^2)의 크기이어야 하지만, 그것은 엉망입니다,
그것은 써야 합니다.
여러분은 이것들을 곱합니다.
그것들이 '| |'의 개념을 가지지 않기 때문에,
엉망입니다.
우리는 그것이 점근적인 개념에 있을 때 '| |'를 둡니다.
그것이 쌍일 때, E는 O(V^2) 입니다.
그것이 쌍의 집합이면,
그것은 최대 n입니다.
여기서 그것은 최대 V^2
나누기 2 입니다.
그리고, 다른 속성은, G가 연결되면,
우리는 다른 바운드를 가지고,
E의 크기는 V의 크기 – 1 입니다.
그것이 연결되면,
연결된 그래프는 무엇을 의미합니까?
그래프에서 한 정점에서 다른 정점으로의 경로가 있습니다.
그것을 연결된 것이라 합니다.
그것이 케이스이면,
엣지의 수는 적어도 정점 – 1 입니다.
저는 여러분에게
상기시키고 싶습니다,
그 케이스에서,
제가 lg|E|를 보면, 엣지 수의 로그는 로그 V의 O입니다.
이것에 의해서, lg V의 오메가입니다.
그러니까 그것은 θ(lg V)의 세타와 같습니다
기본적으로 연결된 그래프에서,
엣지의 수와 정점의 수는
다항적으로 연관이 있습니다.
로그는 비교할 수 있습니다. 그것은 도움이 됩니다
왜냐하면 저는 여러분에게 질문을 할 것이기 때문입니다,
여러분은 그것이 lg|E|라는 것을 보여주었지만 여러분은 그것이 lg V인 것을 보여주지 않았습니다.
저는 그것이 같은 것임을 지적할 수 있습니다.
컴퓨터에서 그래프를 나타낼 수 있는 다양한 방법들이 있습니다,
그리고 저는
중요한 것들을 다룰 것입니다.
사실 더 있습니다. 우리는 더 볼 것입니다.
가장 간단한 것은 인접 행렬입니다.
그래프 G의 인접 행렬은 (V,E)와 같습니다.
간단히 하기 위해, 저는 V를 1에서 n까지 정수의 집합으로 둘 것입니다.
그것은 n 곱하기 n 행렬 A입니다.
A[i,j]에 엣지가 있으면 1이고,
그렇지 않으면 0입니다.
그것이 행렬에 있으면
ij 엔트리는 1입니다.
어떤 면에서,
i에서 j까지의 엣지가 있습니까?
술부는 0 또는 1의 Boolean 공식입니다,
이 케이스에서,
i에서 j까지가 엣지가 있으면 1이고 그렇지 않으면 0입니다.
때때로 여러분은
엣지 중심 그래프를 갖습니다,
그리고 때때로 사람들이 하는 것은 이것을 엣지의 무게로 교체하는 것입니다.
그것은 i에서 j까지의 엣지의 무게입니다.
우리의 직관을 수학적인 정의와 일치시키기
위해 예를 들어 봅시다.
예제 그래프가 있습니다. 우리의 그래프라고 합시다.
인접 행렬을 그립시다.
i에서 j까지의 엣지가 있습니까?
답은 아니오죠.
1에서 2까지의 엣지가 있습니까?
네. 1에서 3까지의 엣지가 있습니까?
네.
1에서 5까지의 엣지가 있습니까?
아니요. 2에서 1까지의 엣지가 있습니까?
아니요.
2에서 2는요? 없습니다.
2에서 3은요? 있습니다.
2에서 4는요? 없습니다.
3의 밖으로 가는 엣지는 없습니다.
4에서 3까지입니다. 그것은 이 특정 그래프를
위한 인접 행렬입니다.
저는 그래프를 이 인접 행렬로 표현할 수 있습니다.
제가 그것을 이 방법으로 표현할 때, 저는 얼마나 많은 저장이 필요한가요?
n^2 또는 V^2 입니다 왜냐하면 크기는 V^2 저장을 위해 같기 때문입니다.
그것은 빽빽한 표현입니다.
그것은 그래프가 빽빽할 때 잘 동작합니다.
엣지의 수가 가능한 모든 엣지와 같으면 그래프는 빽빽합니다.
이것은 좋은 표현입니다.
그러나 많은 그래프 타입을 위해, 엣지의 수는
가능한 모든 엣지 수 보다 더 작습니다,
어떤 케이스에서 우리는 그래프가 드물다고 말하나요?
드문 그래프의 예를 줄 수 있나요?
저는 그래프의 계층을 원합니다 n이 커질수록,
그래프에서 엣지의 수는 정사각형처럼 커지지 않지만
더 작은 것처럼 커집니다.
여러분이 이론적으로 그것을 그래프로부터 보면,
연결 리스트, 연쇄는
좋은 예입니다.
길이 n의 연쇄를 위해 n 엣지가 있습니다.
그러므로, 엣지의 수는 오더 V입니다.
특히, 여러분은 열 당 하나의 엣지를 갖습니다.
다른 드문 그래프가 있나요? 네?
좋아요.
평면 그래프입니다
그것은 오더 V 엣지입니다.
흔한 그래프의 예가 또 있나요?
이진 트리, 부록에 있는
자유 트리가 있습니다.
연결된 그래프인 트리는 원을 가지지 않습니다.
그것은 또 다른 예입니다. 빽빽한 그래프의 예는 무엇이죠?
완전한 트리입니다.
여러분이 엣지 중심을 가지면,
그것은 행렬에 완전히 채워집니다.
좋아요. 이것은 빽빽한 표현을 위해 좋습니다.
그러나 때때로 여러분은 드문 표현을 원합니다
그래서 우리는 V^2 공간을 쓰지
않아도 됩니다,
대부분은 0이 될 것입니다.
그것이 0인 것을 알면, 그것을 0으로써 왜 표현하나요?
그 표현은 인접 리스트
표현입니다.
사실, 인접 리스트는 리스트입니다,
우리는 Adj[v]를 V의 인접한 정점으로 표시합니다.
그것의 용어의 관점에서, 정점은 인접합니다,
그러나 엣지는 정점에서 부수적입니다.
발생 정도는 정점과 엣지 사이의 관계입니다.
인접함은 두 정점 간의 관계입니다.
그것은 단지 언어입니다.
왜 그들은 다른 용어를 사용하나요? 모르겠지만,
그것은 그들이 하는 것입니다.
예를 들어, 그래프에서, 정점 1에 대해서
인접 리스트는 리스트 또는 {2, 3}입니다
1은 2와 3의 엣지이기 때문입니다.
2에 대한 인접 리스트는 {3}이고,
3에 대해서는 빈 집합이네요.
4에 대해서는 {3}입니다.
그것은 표현입니다.
우리가 저장이 얼마나 요구되는지 알면,
우리는 인접 리스트가 얼마나 긴지 이해할 필요가 있습니다.
한 정점 V를 위한 인접 리스트의
길이는 무엇입니까?
그것의 이름은 무엇입니까? 그것은 차수입니다.
무방향 그래프에서, 우리는 그것을 정점의 차수로 부릅니다.
이것은 무방향입니다.
네.
그것은 무방향 케이스입니다. 방향 케이스에서,
우리가 이것을 하는 방법은 이것입니다.
우리는 그것을 방향 그래프를 위한 정도 밖에 있다고 합니다.
방향 그래프에서,
우리는 진입 차수와 출력 차수를 가집니다.
여기서 진입 차수는 3입니다.
여기서 출력 차수는 2입니다.
여기서 중요한 부명제는 핸드셰이킹 부명제입니다.
그것은 수학적인 부명제의
하나입니다.
그것을 이야기로부터 옵니다.
저녁 파티에 가서, 모든 사람은 악수를 합니다.
사람들은 악수를 하지 않을 수도 있습니다.
어떤 사람은 여러 사람과 악수를 합니다.
아무도 스스로와 악수하지 않습니다.
저녁 파티 동안 어떤 점에서,
주인은 가서 얼마나 많은 사람이
악수를 했는지 셉니다.
그는, 당신은 몇 명과 악수했나요? 라고 말합니다.
몇 명과 악수했나요? 몇 명과 악수했나요?
그리고 더합니다.
그것은 보장된 수입니다.
그것은 핸드셰이킹 부명제입니다.
또는 더 정확하게,
제가 어떤 그래프 차수를 취하고, 모두 더하면,
얼마나 많이 악수를 했나요?
그것은 항상 엣지 수의 두 배입니다.
왜 그렇죠?
왜 엣지 수의 두 배인가요?
네? 네.
여러분이 엣지에 넣을 때 마다,
여러분은 1을 마지막에 각 사람의 차수에 다합니다.
그것은 엣지의 같은 수를 세는 두 다른 방법입니다.
여러분이 그것을 상상할 수 있을겁니다. 제가 돌아다니면서,
제가 노드의 차수를 셀 때 마다,
저는 모든 엣지에 표시합니다.
제가 다 하면, 모든 엣지는 두 기호를 가집니다,
매우 간단한 정리입니다.
무방향 그래프를 위해, 인접 리스트 표현은
얼마나 많은 저장을 사용하나요?
최대, 2E입니다, 그래서 오더 E입니다 왜냐하면 그것이 전부가 아니기 때문입니다.
그래서 여러분은 정점의 수 더하기 오더
대각선의 수를 가져야 합니다.
그것이 방향성이든 무방향성이든, 제가 그래프를 가지기 때문에,
그것은 전체 정점을 가지고 대각선을 가지지 않습니다,
그것은 여전히 오더 V의 비용이 듭니다.
그것은 θ(V+E)의 공간을 사용합니다.
그것은 기본적으로 점진적으로 같은 것입니다.
사실 방향 그래프의 관점에서 보는 것은 더 쉽습니다
왜냐하면 제가 모든 차수를 더하면 그것은 E와 같기 때문입니다.
사실 이것은 일종의 분할 상환 분석입니다.
제가 엣지의 총 수를 더하면,
그것을 하는
하나의 방법은
정점을 하나씩 세는 것입니다.
각 정점에 대하여 저는 기본적으로 각 차수와 정점을 가지고,
차수를 봅니다,
그리고 엣지의 두 배로 끝납니다.
그것은 정확히 우리가 분할 상환 분석을 위해
하는 분석의 타입입니다.
우리는 그것을 볼 것입니다.
이것은 드문 표현입니다. 그리고 그것은 종종 인접 행렬 보다
더 낫습니다. 예를 들어,
여러분은 월드 와이드 웹이
인접 행렬로 되는지
상상할 수 있습니다.
월드 와이드 웹에서
모든 링크는 제가 연결하는 것이고,
이것은 제가 연결하지 않는 모든 것입니다.
여러분이 주어진 페이지에서 연결하지 않는 것은
매우 극적으로 여러분에게 드문 표현의
이점이 있다는 것을 보여줍니다.
다른 한편으로,
인접 행렬 표현에 대해 좋은 것은
각 엣지가 단일 비트로 표현될 수 있다는 것입니다,
반면에 제가 이것들을 인접 리스트로 표현할 때,
저는 각 인접을 표현하기 위해
얼마나 많은 비트가 필요합니까?
여러분은 각 정점을 이름 지을 수 있는 오더 lg V가 필요합니다.
수의 오더는 제가 필요한 비트의 수입니다.
이것은 사실 더
효율적인 표현이 있는 곳입니다.
특히, 여러분이 빽빽한 그래프를 가지고 있으면,
이것은 그것을 표현하는 더 나은 방법입니다.
우리는 이것을 다음주에 더 볼 것입니다,
그것은 행렬과 그래프입니다.
같은 것을 보는 두 방법이 있습니다.
사실 여러분이 인접 행렬을 곱할 때
많은 그래프 이론이 있습니다.
그래서
그래프와 행렬 간의 많은 공통점이 있고,
그것이 하나에 적용되면 다른 것에도 적용됩니다.
질문 있나요?
좋아요.
그것은 단지 복습입니다. 이제 저는 오늘의 강의로 들어가고 싶습니다.
그래프에 대한 질문 있나요?
이것은 부록 B를 복습하기 좋은 시간입니다.
저기 많은 훌륭한 속성들이 있고
특히
오늘 우리가 다룰 정리가 있습니다.
그것은 트리의 속성입니다.
트리는 매우 특별한 그래프입니다.
저는 여러분이 속성이 무엇인지 보길 원합니다.
모두 동등한 6개의
다른 트리의 정의가 있습니다.
저는 그 정리를 읽는 것이 좋은 생각이라고 생각해요.
우리는 그것을 수업에서 증명하지 않을 것이지만
우리가 오늘 할 것에 대해 생각하기
위한 좋은 기초를 제공합니다.
그리고 우리는 미래에 많은 것을 볼 것입니다.
우리는 최소 스패닝 트리에 대해 이야기할 것입니다.
이것은 세계에서 가장 중요한 알고리즘 중의 하나입니다.
그것은 분산 시스템에서 중요합니다.
그것은 거의
대부분 분산 시스템이 찾으려고
하는 첫 번째 것 중 하나입니다.
그리고 알고리즘을 개발한 사람은,
나중에 이야기하겠습니다,
그것은 수년 간 AT&T를 위한 시스템의 기초였습니다.
그래서 매우 중요한 것입니다.
그것은 응용의 큰 수를 가집니다.
그래서 문제는 다음과 같습니다.
여러분은 무방향 그래프를 연결했습니다
G = (V,E) 입니다,
w는 엣지를 무게로 매핑합니다.
오늘 강의에서
우리는 중요한 가정을 할 것입니다.
단순함을 위해서요. 책은 이 가정을 하지 않습니다
저는 여러분이 대안 발표를 보았으면 좋겠어요
그들이 책에서 하는 것은 더 일반적이지만,
단순함과 직관을 위해,
저는 이것을 더 쉽게 할 것입니다.
우리는 모든 엣지 무게가 개별적이라고 가정할 것입니다.
모든 엣지 무게는 개별적입니다.
그것은 무엇을 의미하나요?
그것이 의미하는 것은 이 함수입니다.
모든 엣지 무게가 개별적이면 함수는 어떤 속성을 가지나요?
신중한 수학을 기억하나요?
그것은 단사상입니다. 그것은 하나에서 하나로 입니다.
그것은 필수적이지 않습니다.
사실 그것은 하기 어려운 것입니다 왜냐하면 그것은 큰 집합이지만
그것은 하나에서 하나로이기 때문입니다.
그것은 단사상입니다. 그것은 우리가 단순함을 위해 가정하는 것입니다.
책은 그것을 가정하지 않습니다.
그것은 여러분이 그것을 진술해야 하는 방법이
더 정확하다는 것을 의미합니다.
그것은 기술적으로 더 정확해야 합니다.
그것은 입력입니다.
출력은 스패닝 트리입니다. 스패닝 트리에 의해,
우리는 그것을 모든 정점과 연결시킵니다.
그리고 그것은 최소 무게를 가집니다.
그래서 우리는 트리의 무게를 쓸 수 있습니다,
그것에 의해, 우리는 트리에 있는
모든 엣지 합을 충족시킵니다.
I'(V,E)는 잘못된 표현인데,
제가 써야 하는 것은 엣지 w(u,v)입니다
왜냐하면 이것은 엣지로부터 매핑하기 때문입니다,
그것은 저에게 두 괄호를 줍니다.
저는 표현을 남용하길 좋아합니다.
저는 그것을 남은 괄호에 둘 것입니다,
왜냐하면 우리는 그것이 정말 엣지의 무게라는 것을 이해하기 때문입니다.
정렬된 쌍의 무게가 아닙니다.
그것은 작은 표현적인 편리함입니다.
시험을 볼 때, 개념적인 편리함은
차이를 만들고,
쉽습니다.
그것은 여러분이 문제에서 답을 쓸 때 사용하는 표현에 대해
생각할 가치가 있습니다.
일반적으로, 여러분은
좋은 표현을 채택합니다.
여러분은 나쁜 표현을 채택하면 아무도 주의를 기울이지 않습니다
그들은 여러분이 말하는 것을 이해하지 못하기 때문입니다.
예를 해 봅시다.
여기 그래프가 있습니다.
누군가 제게 생물화학에서 영감을 받았냐고 물었지만,
저는 그렇지 않습니다.
단지 이것들을 썼습니다.
여기 그래프가 있습니다. 그리고 우리에게 엣지 무게를 줍니다.
몇 엣지 무게들이 있습니다.
우리가 원하는 것은 트리를 찾는 것입니다.
모든 정점이 트리의 일부인 연결된 비순환 그래프입니다.
그러나 그것은 가능한 최소 무게를 갖지 않습니다.
이 최소 스패닝 트리에서
엣지가 무엇인지 제안할 수 있나요?
9입니다, 좋아요.
9는 저기 있어야 합니다. 왜죠?
그것은 그것과 이 정점을 연결하는 유일한 것이기 때문입니다.
15 는 저기 있어야 합니다.
모두 저기 있어야 합니다.
다른 엣지는 어디 있어야 하나요?
14는 그것이어야 합니다. 왜 14는 거기 있어야 하나요?
14의 하나와 3은 저기 있어야 합니다.
저는 무게를 최소화하길 원합니다. 전반적으로 가장 작은 무게를 가지는 것입니다.
3이 저기 있다고
주장할 수 있나요?
네? 그것은 2의 최소값입니다,
그것은 여러분이 무엇을 더하면
그것이 14를 포함한다고 말합니다.
그리고 저는 이 엣지를 지울 수 있고,
엣지에 3을 넣습니다. 저는 더 낮은 무게를 가집니다.
3은 저기 있어야 합니다.
저기 다른 엣지가 무엇이어야 하나요?
복잡한 논리를 해 봅시다. 6과 5는 저기 있어야 합니다.
그것들은 왜 저기 있어야 하나요?
그것은 이를 통해 연결될 수 있습니다.
그것은 필수적으로 이 길로 가지 않습니다.
6은 3이 저기 있어야 하는 같은 이유로
저기 있어야 합니다.
우리가 두 선택을 가지기 때문입니다.
모든 것이 연결되지만 그것이 12가 아니면,
12는 저기
있었습니다.
그것을 이 길로 대신 연결합시다.
분명히 그것은 저기 있습니다.
저는 여전히 연결된 모든 것을
가지지 않습니다.
최소 스패닝 트리를 위해 무엇이 있어야 합니까?
7 5 8 입니다, 왜죠?
이것을 한번에 할 수 있나요?
왜 5는 저기 있어야 하나요?
네?
우리는 연결된 4 성분을 가집니다
우리가 이것을 가지기 때문입니다,
우리는 사실 이것을 여기서 가집니다.
우리는 적어도 그것들을 연결하기 위해 세 엣지가 필요합니다
왜냐하면 각 엣지는 연결된 성분을 줄일 것이기 때문입니다.
그래서 우리는 세 엣지가 필요하고,
그것들은 가장 싼 것입니다.
그리고 그것들은 작동합니다. 그것들은 작동합니다. 그렇죠?
더 큰 다른 엣지가 있나요?
네. 이제 우리는 스패닝 트리를 가지나요?
우리는 여기서
큰 연결된 그래프를 가집니다.
그것은 제가 가지는 것인가요? 그것은 제가 가지는 것과 같습니다.
삶은 예측 가능합니다.
모두 최소 스패닝 트리가 무엇인지
알고 있나요,
저기서 무엇을 하나요? 먼저
이 퍼즐에 대해 봅시다.
제가 원하는 것은 여러분에게 최적 서브 구조 속성에 대해 상기시키는 것입니다
왜냐하면 최소 스패닝 트리는
좋은 최적의 서브 구조 속성을 가지기 때문입니다.
우리는 최소 스패닝 트리를 가질 겁니다.
그것을 T라고 합시다.
저는 그래프에서 다른 엣지와
그것들을 보여줄 것입니다.
여기 그래프가 있습니다.
여기 그래프가 있습니다. 그것은 여기서 제 종이를 가지는 것과 같습니다.
이것은
최소 스패닝 트리입니다.
이제 우리는 최적 서브 구조의 속성을 보길 원합니다.
제가 그것을 얻는 방법은,
어떤 엣지를 제거하고,
임의의 엣지를 움직이는 것입니다.
이것을 u라고 하고 이것을 v라고 합시다.
우리는 이 엣지를 제거할 것입니다.
제가 트리에서 엣지를 제거할 때,
트리에 무슨 일이 일어납니까?
왼쪽은 무엇입니까?
저는 왼쪽에 두 트리를 가집니다. 저는 왼쪽에 두 트리를 가집니다.
그것은 기본적으로 부록에 있는
속성의 하나입니다.
트리의 속성들을 읽어보세요, 여러분이 그것을 명확히 하기 보다는
그것을 증명할 수 있기 때문입니다.
우리는 그것을 제가합니다.
T는 두 서브 트리로 분할됩니다.
우리는 그것을 T_1와 T_2으로 부릅니다.
여기 하나의 서브 트리가 있고 다른 하나의 서브 트리가 있습니다.
우리는 그것을 분할 했습니다. 제가 어떤 엣지를 고르든,
그것이 분할 되는 두 서브 트리가 있습니다.
예를 들어, 서브 트리가 사소한 서브 트리라고 하더라도,
그것은 단일 노드를 가지고
엣지가 없습니다.
우리가 증명할 정리는 최적 서브 트리의 속성을 증명합니다.
T_1은 그래프를 위한 최소 스패닝 트리입니다.
G의 서브 그래프는
T_1에서 정점에 의해 유발됩니다.
V_1은 T_1에서 정점입니다,
그리고 그것은 유발된 것을 의미합니다. V_1은 T_1에서 정점입니다.
이 그림에서,
저는 그것에 라벨을 붙이지 않았습니다. 이것은 T_1이고
이것은 T_2 입니다. 이 그림에서,
이것들은 T_1의 정점입니다. 그것은 V_1입니다.
그리고 E_1은 정점의 쌍의 집합입니다,
그것은 V_1에 속하는
x와 y가 E_1에 있는 엣지입니다.
저는 여기서 G의 엣지를 보여주지 않았습니다.
기본적으로, 엣지가 여기서 여기로 갔으면,
그것은 E_1에 있습니다.
그것이 여기서 여기로 갔으면,
그것은 그렇지 않습니다.
서브 그래프는 T_1에서 연결하는 것입니다,
T_2에서도 유사합니다.
제가 그래프 G_1 내에서 엣지를 보면,
그것들은 이 정점에 의해 유발됩니다,
그것은 사실
그 서브 그래프를 위한 최소 스패닝 트리입니다.
그것은 정리가 말하는 것입니다. 제가 이 집합에 의해 유발된
엣지의 집합을 보면
T_2는 그 서브 그래프에서
최소 스패닝 트리입니다.
우리는 그것을 여기서도 할 수 있습니다.
제가 이것들을 보면, 예를 들어
제가 엣지5를 자르면,
T_1은 이 4 정점이 됩니다.
제가 서브 그래프를 보면,
여기 엣지가 있습니다.
사실 6 8 3은 모두 그 서브 그래프를
위한 최소 스패닝 트리에서 엣지입니다.
그것은 정리가 말하는 것입니다.
그것을 증명합시다.
그것을 증명하기 위해 우리가 사용하는 기술은 무엇입니까?
우리는 이 기술을 지난 시간에 배웠습니다.
그것은 여러분이 항상 문서 편집기에서 해야 하는 것,
복사와 붙여넣기 입니다.
T의 무게는
제가 제가하는 엣지의 무게
더하기 T_1의 무게 더하기 T_2로 표현할 수 있습니다.
인자는 매우 간단합니다.
그것이 G_1을 위해 T_1 보다
더 나은 T_1 프라임입니다.
제가 스패닝 트리를 형성하는 더 나은 방법을 가진다고 가정해 보세요.
저는 T 프라임을 구성합니다, 그것은
엣지(u,v), 그리고 T_1 프라임,
T_2를 포함했습니다.
제가 더 나은 스패닝 트리를 가지면,
저는 T_1의 더 낮은 무게의 스패닝 트리를 취합니다. 그리고 저는 그것을 T_1 프라임으로 부릅니다.
저는 그것을 빼고 제 엣지로 구성되는 스패닝 트리를 구성합니다,
무엇이 T_1 그리고
T를 위해 잘 동작하든지요.
그리고 그것은 스패닝 트리입니다.
T 보다 낫습니다
이것들의 무게는 이것을 위한 무게이기 때문입니다,
저는 이제 T_1 프라임의 무게를 사용합니다,
그것은 더 적습니다. 그러므로
T가 최소 스패닝 트리라는 가정은 위반됩니다
제가 더 나은 것을 찾으면요.
우리는 최적 서브 구조를 위한 좋은 속성을 가집니다.
저는 서브 문제들을 가집니다,
제가 그 안에 전체 문제의 최적의 답을 가지면,
저는 서브 문제의 최적의 답을 찾을 수 있습니다.
이제 질문은, 그것이 특징이라는 것입니다.
그것은 동적 프로그래밍의 특징입니다.
서브 문제를 오버래핑 하는 것은 어떻습니까?
제가 그 속성을 가지나요? 제가 여기서
이 문제 타입을 위한 서브 문제를 오버래핑 하나요?
예를 들어,
제가 다른 엣지를 제거한다고 가정해보세요.
저는 주어진 엣지를 가지는
공간을 봅니다,
그리고 그것을 제거합니다.
그것은 두 부분으로 나누어지고, 이제 저는 다른 것을 갖습니다. 그리고 그것을 제거합니다.
저는 이와 유사한 많은 서브 문제를 가지나요?
네. 제가 이것을 꺼내면,
이것은 여기 있습니다,
그리고 저는 여기와 여기서 다른 트리를 가집니다.
그것은 제가 원래
이것을 꺼낸 것과 같습니다.
제가 엣지를 꺼내는 간단한 순서를 보면,
저는 서브 문제를 오버래핑하는 많은 문제로 마칩니다.
좋아요.
그래서 그것은 무엇을 제안하나요?
동적 프로그래밍 입니다. 좋아요.
여러분은 동적 프로그래밍을 사용할 수 있습니다.
그러나 그것은 최소 스패닝 트리가
더 강력한 속성임을 말합니다.
우리는 동적 프로그래밍을 위한 단서를 가지지만
우리에게 더 강력한 기술을 사용하도록
돕는 더 큰 단서들이 있습니다.
우리는 탐욕 알고리즘을 위한 특징을
부릅니다.
우리는 탐욕 선택 속성이라는 것을 가집니다,
지역적으로 최적의 선택은
전체적으로 최적입니다.
물론, 이 모든 특징이 여러분이 원하는 것이면,
이것들이 여러분이 할 수 있는
단서들이기 때문입니다.
우리는 탐욕 선택 속성이라는 이 속성을 가집니다.
저는 여러분에게 이 케이스에서 그것이 동작하는 방법을 보여줄 것입니다.
여러분이 탐욕 선택 속성을 가질 때,
여러분은 더 나은 동적 프로그래밍을 할 수 있습니다.
여러분이 두 동적 프로그래밍 속성을 볼 때,
단서가 있지만,
그것이
탐욕 속성을 또한 가지는지 봅시다,
가진다면, 여러분은
더 나은 동적 프로그래밍인 것을 떠올립니다.
여러분이 둘을 가지면, 여러분은 보통 동적 프로그래밍을 할 수 있지만,
여러분이 이 세 번째를 가지면,
잭팟입니다!
여기 우리가 이 생각을 증명할 정리가 있습니다.
이것들은 아무것도 아닙니다.
그것들은 휴리스틱입니다.
저는 여러분에게 알고리즘을 줄 수 없습니다,
여기 동적 프로그래밍이 작동하고, 여기서 탐욕 알고리즘이 작동합니다.
그러나 저는 그것들이
작동할 때를 지시합니다.
여기 정리가 있습니다. T를 우리 그래프의 MST라고 합시다.
그리고 A를
V의 서브 집합이라고 합시다.
(u,v)는 우리의 집합 A를 A의 성분과 연결하는
최소 무게 엣지입니다.
즉, V – A 입니다.
(u,v)는 최소 스패닝 트리입니다.
여기서 우리의 그래프를 봅시다.
그리고 그것이 이 케이스인지 봅시다.
우리가 A를 위해 할 수 있는 것
하나는 개체 노드를 가지는 것입니다. 저는 개체 노드를 가집니다,
그것은 제 A가 될 수 있고,
모든 것은 V – A 입니다.
저는 이것과 다른 모든 것을 연결하는 최소 무게 엣지를 봅니다.
그것과 다른 모든 것을 연결하는
두 엣지가 있습니다.
더 가벼운 것은 최소 스패닝 트리에 있습니다.
제가 이겼습니다.
여러분이 모든 정점을 보면,
정점으로부터 나오는 가장 마지막 엣지를 최소 스패닝 트리에 있습니다.
가장 가벼운 무게의 엣지입니다,
그것은 여기 있는 모든 엣지가 아닙니다.
이 집합과 연결된
이 세 정점을 봅시다.
저는 세 엣지를 가집니다.
가장 적은 무게는 5입니다. 그것은 최소 스패닝 트리입니다.
저는 그것을 이 방법으로 자를 수 있습니다.
아래로 가는 엣지는 7 8 14입니다.
7은 최소 무게입니다.
그것은 최소 스패닝 트리에 있습니다.
제가 어떻게 고르든,
저는 이것을 안으로
또는
밖으로 할 수 있습니다.
모든 엣지가 무엇을 하는지 봅시다.
그것은 최소 스패닝
트리에 있습니다.
어떤 면에서, 그것은 지역 속성입니다
저는 트리의 나머지가 무엇인지 보지 않기 때문입니다.
저는 작은 정점 집합만 봅니다,
제가 그것을 나머지와 연결하고 싶으면,
무엇을 고르나요?
저는 가장 싼 것을 고릅니다. 그것은 탐욕 접근입니다.
그것은
그 서브 집합을 위해 지역적으로 좋고,
전체적으로도 좋습니다. 그것은 전체 함수를 최적화합니다.
정리가 말하는 것이 무엇입니까?
이 정리를 증명합시다.
이에 대한 질문 있나요? 이 정리를 증명합시다.
(u,v)는 A 에서 D minus A 를 연결하는 최소 무게 엣지입니다.
(u,v)가
최소 스패닝 트리에 있지 않다고 가정합시다.
이 최소 무게 엣지를 포함하지 않는
최소 스패닝 트리가 있다고 가정해보세요.
여기서 모순을 얻는걸 증명하기 위해 무슨 기술을 사용할 것인가요?
복사와 붙여넣기 입니다.
우리는 복사와 붙여넣기를 할 것입니다.
우리는 복사와 붙여넣기를 할 것입니다.
여기서 저는 예를 했습니다,
그리고 저는 개념을 사용할 것입니다.
저는 이것에 색을 입힐 수 있습니다.
여기서의 개념은 이것이 A의 인자라는 것입니다.
그것은 of V minus A의 인자입니다.
그것이 색을 입히지 않으면, 그것은 A입니다.
이것은 제 최소 스패닝 트리입니다.
다시 한번, 제가 모든 그래프의 전체적인 엣지를 보여주지 않지만,
그것들은 거기 있습니다.
그래서 제 엣지 (u,v)는 제 최소 스패닝
트리가 아닙니다.
그것은 u로부터의 엣지이고, A에서 u이고, V minus A에서 v입니다.
모두 설정을 보나요? 저는 엣지가
최소 스패닝 트리에 있어야 한다는 것을 증명하고 싶습니다.
이것은 최소 스패닝 트리이고
(u,v)를 포함하는 것은 틀렸습니다.
제가 원하는 것은 저는 여기서 트리를 갖습니다,
저는 두 정점 u와 v를 갖습니다,
두 정점 간에 유일한, 간단한 경로가 있습니다.
그것은 엣지와 정점을 반복하지 않습니다.
u에서 v까지 유일한, 간단한 경로가 있습니다.
그 경로를 고려해 봅시다.
그 경로는 존재합니다 교재의
부록 B.5.1을 보세요.
그것은 트리의 속성에 대한 좋은 정리입니다.
그것은 유일한, 간단한 경로가 존재하는 방법입니다.
이제 우리가 하려고 하는 것은
그 경로를 보는 것입니다. 이 케이스에서,
그것은 여기서부터 여기로 갑니다.
그 경로를 따라
제가 A에서 정점과 V minus A에서 정점을 연결하는 점이 있습니다.
왜죠?
이것이 A에 있기 때문입니다. 이것은 V minus A에 있습니다.
경로를 따라, 이행이 있어야 합니다.
그것은 모두 A에 있지 않습니다 특히 V가 그렇지 않기 때문입니다.
우리가 하는 것은
(u,v)를 정점을 연결하는
이 경로의 첫 엣지로 바꾸는 것입니다.
이 케이스에서, 그것은 이 엣지 입니다.
저는 A 에서 V minus A로 갑니다. 일반적으로,
저는 많이 대체할 수 있고, 마주치는 첫 번째 것을 골랐습니다.
이것이 여기 있습니다.
그리고 제가 하는 것은 이 엣지를 두는 것입니다.
무슨 일이 일어나나요?
(u,v)는 A에서 무엇을
V minus A로의 무엇과 연결하는 가장 가벼운 것입니다.
특히,
그것은 이 엣지보다 더 가볍습니다, 더 적은 무게를 가집니다.
이것을 바꿈으로써, I'(V,E)는 전반적으로 적은 무게를 가진 트리를 만들었습니다,
그리고 그것은 이 다른 것이 최소 스패닝 트리여야
한다는 가정과 모순됩니다.
T의 결과 보다 더 낮은 무게의 스패닝 트리입니다,
그리고 그것이 모순입니다.
그것이 모순입니다,
그렇죠? 우리는 어떻게 하나요?
모두 알겠나요? 이제 우리는 어떤
알고리즘을 할 것입니다.
우리는 프림 알고리즘을 할 것입니다.
프림은 결국 AT&T에서 매우 높습니다
왜냐하면 그는 이 알고리즘을 최소 스패닝 트리를 위해 고안했기 때문입니다,
그리고 그것은 수년 동안
AT&T를 위한 모든 코드에서 사용되었습니다.
그는 벨 연구소에서 매우 우뚝 섰습니다.
여러분이 해야 하는
모든 것을 알고리즘을 고안하는 것이라는 걸 보여줍니다.
여러분도 회사의 사장이 될 수 있습니다.
물론, 정부는 그것을 독점으로 할 수 있지만,
그것이 삶에서 여러분의 미션이라면,
알고리즘을 고안하세요. 여기 아이디어가 있습니다.
우리가 할 것은 V - A를 우선순위 큐로 유지하는 것입니다.
우리는 그것을 Q라고 할 것입니다.
우리는 Q에서
각 정점을 입력하고, 그것을 A의 정점과 연결합니다.
여기 코드가 있습니다.
우리는 그것을 모든 정점이 되는 Q에서 시작합니다.
우리는 A에서 시작합니다, 그것은 빈 집합입니다.
그것은
최소 무게 엣지이고,
기본적으로 무한대가 됩니다
왜냐하면 그것들은 아무도 엣지를 가지지 않기 때문입니다. 최소 무게 엣지는 비어 있을 것입니다.
그리고 우리는 이것으로 시작할 것입니다.
그것을 S라고 부를 것입니다,
그것은 V에서 임의의 S를 위해 0으로 설정됩니다.
알고리즘의 주요 부분이 효과가 나타나기 시작합니다.
그것은 초기화입니다. 우리가 분석을 할 때,
저는 왼쪽에 무엇을 쓸 것입니다.
여러분이 필기를 할 때,
노트 왼쪽을 남겨두세요.
Q가 빈 반면에,
우리는 그것에서 가장 작은 인자를 얻습니다.
그리고 우리는 무엇을 합니다.
그게 전부입니다. 제가 여기서 언급해야 하는 유일한 것은,
여기서 무엇이 일어나는지 봅시다.
그것은 예에서 돌 것입니다.
우리가 하는 것은
각 단계에서 큐에서 가장 작은 인자를 꺼내는 것입니다.
인접 행렬에서 각 단계를 위해,
즉, v에서 u까지 가는
엣지 입니다,
그리고 v가 여전히 우리의 집합 V - A에 있으면,
우리는 A의 부분에서
꺼냅니다.
그것은 우리가 구축하는 새로운 A입니다.
각 단계에서,
A와 모든 것을 연결하는 가장 싼 엣지는 무엇입니까?
우리는 기본적으로 가장 싼 것을 취하고
그것을 더합니다, 이제 그것을
A로 데려와서 다음으로 가장 싼 것을 찾습니다.
우리는 이 과정을 계속 반복합니다.
우리는 그것을 예에서 할 것입니다.
우리가 그것을 가져올 때 마다 매번,
책임을 가지는 정점이 무엇인지 봅니다.
제가 이 쌍의 집합을 보면,
그것은
최소 스패닝 트리를 형성합니다.
이것을 해 봅시다. 그것은 무엇입니까?
우리는 모두 설정합니다. 그리고 여기서 이것들을 제거합시다.
우리는 그것들을 다시 계산할 것이기 때문입니다.
여러분은 노트에서 다시 그래프를 복사하길 원합니다.
저는 그것을 해야 했지만,
이것은 지울 것입니다.
그것을 수정해 봅시다. 우리는 시작하겠습니다.
우리는 모든 것을 무한대로 만들 것입니다. 그래서 그것은 제가 키 값을 가지는 곳입니다.
그리고 저는 하나의 정점을 찾습니다.
그리고 저는 그것을 S라고 부를 것입니다.
저는 여기서 이 정점을 합니다.
우리는 그것을 S라고 부릅니다. 기본적으로,
저는 그것을 0이 되도록 합니다.
이제 저는 최소값을 추출합니다. 기본적으로
저는 이와 같이 음영을 넣습니다, 783 01:08:28,198 --> 01:08:34,000 그것은 이제 집합 A라는 것을 의미합니다.
이것은 A가 될 것입니다. 그리고 이것은 V - A의 인자입니다.
우리가 하는 것은 보는 것입니다.
우리는 그것을 추출하고,
인접 리스트에서 각 정점을 위하여,
우리는 그것이 여전히
Q,
즉 V - A에 있는지 볼 것입니다.
그렇다면, 그것의 키 값은 엣지의 값 보다 작습니다,
우리는 그것을 엣지 값과 교체할 것입니다.
이 케이스에서,
우리는 이것을 7과 교체할 것입니다.
우리는 이것을 15와 교체할 것이고, 이것을 10과 교체할 것입니다.
우리가 관심 있는 것은, 797 01:09:33,854 --> 01:09:39,608 가장 싼 것이 무엇입니까?
우선순위 큐에 있는 것은
이제 그것과 I'(V,E)가 이미 제거한 것을 연결하는
가장 싼 방법을 가집니다,
그리고 그것은 A에 있는 것입니다.
제가 그것을 업데이트할 때,
이 우선순위 큐에 내포된 것이 있습니다.
그것은 제가 감소된 키를 해야 하는 것입니다.
내포된 키의 감소가 있습니다.
감소된 키는 우선순위 큐에서 키의 값을 낮추는
우선순위 큐 연산입니다.
제가 데이터 구조를 볼 때 저는
그 우선순위 큐를 구현하는 것을 사용합니다.
우선순위 큐를 구현하기 위한 일반적인 데이터 구조는 최소 힙입니다.
저는 실제로 제가 이 연산을 한다고
확신해야 합니다.
저는 그것을 바꿀 수 없고 제 힙에 영향을 미치지 않습니다.
저기서 내포된 연산이 있습니다.
저는 이제 반복합니다. 저는 가장 싼 것을 찾습니다,
그리고 포인터를 설정합니다.
이것은 이 방법으로 포인터를 설정합니다.
이것은 이 방법으로 포인터를 설정하고,
이것은 이 방법으로 포인터를 설정합니다.
그것은 제 값을 설정하는 것을 하는 pi입니다.
우리는 안으로 가고 가장 싼 것을
다시 찾습니다.
그리고 우리는 그것을 빠르게 합니다.
이것이 빠른 알고리즘입니다.
이제 우리는 이것을 다시 할 것입니다. 추출하기 가장 싼 것은 무엇입니까?
이것인가요?
우리는 그것을 가지고
그의 이웃을 모두 업데이트합니다.
이것은 5를 얻습니다. 이것은 12를 얻습니다.
이것은 9를 얻습니다. 이것은 업데이트 하지 않습니다.
왜냐하면 더 이상 우선순위 큐에
있지 않기 때문입니다,
우리는 그것이 초점을 맞추는 것에 초점을 맞춥니다.
우리는 그 단계를 다 했습니다. 이제 우리는 가장 싼 것을 찾습니다.
이제 가장 싼 것은 무엇입니까? 여기 5입니다.
좋아요. 우리는 그것을 꺼냅니다.
우리는 이웃을 업데이트 합니다. 그것은 6으로 갑니다.
우리는 그 포인터를 가집니다.
우리는 이것을 하지 않습니다, 그것이 저기 없기 때문입니다.
이것은 14가 되고, 이것은 8이 됩니다.
우리는 그것을 업데이트 하고
8로 만듭니다. 제가 이것을 옳게 했나요?
네, pi가 이 것의 함수이기 때문입니다.
기본적으로 이것은 사라집니다.
제가 놓친 다른 것을 했나요?
12입니다, 좋아요,
그것은 제거되었습니다. Pi는 단지 함수이기 때문입니다.
그리고 이제 괜찮습니다.
이제 저는 무엇을 하나요? 이제 제 집합 A는
세 가지로 구성되고 저는 가장 싼 엣지를 원합니다.
저는 그것이 최소 스패닝 트리에 있다는 것을 합니다.
탐욕적으로 그것을 고르겠습니다.
이제 가장 싼 것은 무엇입니까?
이것이 나타나나요?
네, 6입니다. 우리는 그것을 가집니다.
우리는 이것들을 업데이트하고, 여기서 아무것도 중요하지 않습니다.
이것들은 이미 A에 있기 때문에 아무것도 바뀌지 않습니다.
이제 가장 싼 것은 8입니다.
우리는 8을 꺼냅니다.
우리는 이것을 업데이트 합니다. 아무 것도 되지 않았습니다.
아무 것도 되지 않았습니다.
14 대신에 우리는 이것을 3으로 합니다.
우리는 그 포인터를 제거하고 그것을 이 방법으로 합니다.
이제 3은 가장 싼 것입니다.
우리는 그것을 꺼내고, 물론 저기 아무 것도 되지 않았습니다.
이제 마지막으로,
저는 9를 가집니다. 그리고 그것은 다 되었습니다.
그리고 15도 되었습니다. 그리고 알고리즘은 종결됩니다.
제가 고른 모든 엣지를 볼 때,
그것들은 정확히 우리가 처음에 가지는 모든 엣지입니다.
여기서 분석을 해 봅시다.
이 부분은 오더 V가 듭니다, 그렇죠?
이 부분은,
우리가 여기서 무엇을 하는지 봅시다.
우리는 이 루프를 몇 번 합니까?
V번 합니다. 그것은 우리가 큐에 넣는 V 인자들입니다.
우리는 아무 것도 삽입하지 않습니다.
우리는 단지 그것들을 꺼냅니다. 이것은 V번 하고
우리는 최소값을 추출하는 수를 합니다.
우리는 오더 V를 합니다.
그리고 인접 리스트로 가서 정수의 것을 가집니다.
그러나 우리는 여기 이것을 위한
내포된 감소 키를 가집니다.
그리고 이것 입니다. 우리는 얼마나 많은 내포된
감소 키를 가집니까?
그것은 비쌀 것입니다.
이 케이스에서, 우리는 그것들의 u의 차수를 가집니다,
우리는 얼마나 많은 내포된 감소 키를 가집니까?
우리는 V번을 가집니다.
u의 차수는 얼마나 클 수 있습니까?
그것은 V, order V만큼 큽니다.
그것은 V^2입니다. 그러나 우리는 그것보다 더 나은 바운드를 할 수 있습니다.
우리는 실제로 얼마나 가지나요?
최대 오더 E입니다 저는 무엇을 하나요?
저는 모든 정점의 차수를 더합니다.
그것을 제가 그것들을 실행하는 횟수입니다.
저는 오더 E를 가집니다.
전반적인 시간은
오더 V입니다.
이제 데이터 구조를 봅시다, 우리는 이 공식이 우리에게 주는
다른 데이터 구조를 평가할 수 있습니다.
우리는 데이터 구조를 실행하는 다른 방법을 가집니다.
우리는 최소값을 가지고 감소 키를 가집니다.
데이터 구조를 구현하는 가장 간단한 방법은
정렬되지 않은 배열입니다.
제가 정렬되지 않은 배열을 가지면, 최소 인자를 추출하는데 얼마의 시간이 걸립니까?
제가 정렬되지 않은 배열을 가지면요?
이 케이스에서 오더 V입니다 왜냐하면 그것은 크기 V의 배열이기 때문입니다.
감소 키를 하기 위해 저는 그것을 오더 1에서 할 수 있습니다.
총 비용은 오더 V^2입니다.
사람들이 제안했던 것처럼, 이진 힙은 어떤가요?
이진 힙에서 최소를 추출하기 위해 얼마의 비용이 드나요?
오더 로그 V입니다. 여러분은 그것을
오더 로그 V에서 할 수 있습니다
왜냐하면 기본적으로 여러분은 값을 섞을 수 있기 때문입니다,
그것을 루트와 바꿀 수 있습니다.
또는 로그 V에서요. 그러므로 총비용은요?
E log V 입니다.
어느 것이 더 낫나요? 상황에 따라 다릅니다.
언제 하나가 더 낫고, 다른 것이 더 낫나요?
그것이 빽빽한 그래프이면 E는 V^2와 가깝습니다, 배열은 더 낫습니다.
그러나 그것이 드문 그래프이면,
E는 V^2 보다 훨씬 더 작습니다, 그리고 이진 힙이 낫습니다.
그것은 피보나치 힙이라는 데이터 구조의 고안을 동기 부여 시켰습니다.
피보나치 힙은 CLRS의 20장에서 다루어집니다.
우리는 내용을 하지는 않지만
흥미로운 데이터 구조입니다 그것이 분할 상환 데이터 구조이거든요.
그것은 데이터 구조이고,
여러분은 order log V
분할 상환 시간에 최소를 추출할 수 있습니다.
그리고 주목할만 하게, 여러분은 오더 1 분할상환에서 감소 키를 합니다.
제가 이것들을 연결할 때,
저는 무엇을 얻나요?
그것은 무엇이 되나요? 그것을 여기서 연결합시다.
그것은 V 곱하기 log V 더하기 E: E 더하기 V log V 입니다.
이것들은 분할 상환이고, 이것은 무엇입니까?
까다로운 질문입니다. 그것은 최악의 케이스입니다.
그것은 여기서 분할 상환이 아닙니다. 이것들은 분할 상환이지만
그것은 분할 상환의 미입니다.
그것은 최악의 케이스가 될 수 있습니다.
E 더하기 V log V. 제가 제 연산의 분할 상환 비용을 더할 때,
그것은 옳은 비용에서 상계이기 때문입니다.
이 분할 상환 분석의 미 중 하나는
다른 비용을
다른 연산에 할당 할 수 있는 것입니다
저는 그것들을 더할 수 있고 제 최악의 케이스 비용을 얻습니다.
이것은 이미 V log V입니다. 제가 여러분에게
가도록 하기 전에 다른 알고리즘들이 있습니다.
책에 있는 Kruskal 알고리즘은 분리 집합 데이터 구조라는
분할 상환 데이터 구조를 사용합니다,
그것은 또한 E log V에서 돕니다,
즉, 이 시간에서 돕니다, 이진 힙을 사용하는 것과 같습니다.
저는 책을 언급할 것입니다. 956 01:23:00,000 --> 01:23:04,935 이 문제를 위한 가장 좋은 알고리즘은 우
리 학교 졸업생이자 교수인 David Karger,
브라운 대학 교수인 Phil Kline,
1993년에 프린스턴 교수였고
모든 데이터 구조의 마스터인 Robert Tarjan에 의해 이루어졌습니다.
그것은 랜덤 알고리즘이고,
오더 V 더하기 E를 줍니다. 그것은 최고입니다.
결정적인 것에 대해여 아직 열려있습니다,
선형 시간인 최악의 케이스 바운드에 대해서요.
그러나 선형 시간에 랜덤이고,
그렇지 않으면,
이것은 추가 가정 없이 필수적으로 최고의 바운드입니다.
매우 좋은 것입니다.
다음으로, 우리는 탐욕과
동적 프로그래밍의 많은 아이디어를 볼 것입니다.