TADM2E 5.12 - Revision history

Matt: Undo revision 1145 by FuckyouMatt (talk)

2020-08-02T12:09:59Z

Undo revision 1145 by FuckyouMatt (talk)

FuckyouMatt: Blanked the page

2020-08-02T02:11:21Z

Blanked the page

Bkarpov96: Undo revision 885 | Why are u doing this? What's the point? It's wiki for learning book

2020-07-23T08:14:09Z

Undo revision 885 | Why are u doing this? What's the point? It's wiki for learning book

Fucs: Undo revision 867 by Bkarpov96 (talk)

2020-07-22T22:54:02Z

Undo revision 867 by Bkarpov96 (talk)

Bkarpov96: Undo revision 801 by EthanGamer (talk)

2020-07-22T11:21:17Z

Undo revision 801 by EthanGamer (talk)

EthanGamer: Blanked the page

2020-07-14T02:00:58Z

Blanked the page

Bkarpov96: Translation fixes

2020-06-30T07:55:16Z

Translation fixes

Bkarpov96: Adding signature to solution

2020-06-30T07:48:39Z

Adding signature to solution

Bkarpov96: Solution of 5.12

2020-06-30T07:48:08Z

Solution of 5.12

New page

<pre>Algorithm:
BFS of each vertex v ∈ V, O(|V| * (|V| + |E|))
Saving adjacent vertexes to an adjacency matrix or adjacency list O(1)

Extensions:
BFS stops at a depth of 2
- Depth 1-adjacent v in the original orgaf
- Depth 2-adjacent v in the orgaf square
BFS uses the vertex statuses unopened, open, and processed
- Open and processed vertexes are not added to the queue again

Time complexity of the algorithm O (|V| * (|V| + |E|)) = O((|V|)^2 + |V * E|)) = O(|V * E|)
- The number of edges does not grow slower than the number of vertexes
- In a graph of 1 vertex, when adding 1 vertex, 1+ edge is added
- In a complete graph of n vertices, the number of edges is determined by the Handshaking lemma
- - For a complete orgaf |E| = n * (n - 1) edges
- - For a complete neorgaph |E| = n * (n - 1) / 2 edges</pre>

← Older revision		Revision as of 02:11, 2 August 2020
Line 1:		Line 1:
−	~~<pre>Algorithm:~~
−	~~BFS of each vertex v ∈ V, O(\|V\| * (\|V\| + \|E\|))~~
−	~~Saving adjacent vertexes to an adjacency matrix or adjacency list O(1)~~

−	~~Extensions:~~
−	~~BFS stops at a depth of 2~~
−	~~- Depth 1-adjacent v in the original graph~~
−	~~- Depth 2-adjacent v in the graph square~~
−	~~BFS uses the vertex statuses unopened, open, and processed~~
−	~~- Open and processed vertexes are not added to the queue again~~
−
−	~~Time complexity of the algorithm O (\|V\| * (\|V\| + \|E\|)) = O((\|V\|)^2 + \|V * E\|)) = O(\|V * E\|)~~
−	~~- The number of edges does not grow slower than the number of vertexes~~
−	~~- In a graph of 1 vertex, when adding 1 vertex, 1+ edge is added~~
−	~~- In a complete graph of n vertices, the number of edges is determined by the Handshaking lemma~~
−	~~- - For a complete directed graph \|E\| = n * (n - 1) edges~~
−	~~- - For a complete not directed graph \|E\| = n * (n - 1) / 2 edges</pre>~~
−	~~--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 07:48, 30 June 2020 (UTC)~~

← Older revision		Revision as of 22:54, 22 July 2020
Line 1:		Line 1:
−	~~<pre>Algorithm:~~
−	~~BFS of each vertex v ∈ V, O(\|V\| * (\|V\| + \|E\|))~~
−	~~Saving adjacent vertexes to an adjacency matrix or adjacency list O(1)~~

−	~~Extensions:~~
−	~~BFS stops at a depth of 2~~
−	~~- Depth 1-adjacent v in the original graph~~
−	~~- Depth 2-adjacent v in the graph square~~
−	~~BFS uses the vertex statuses unopened, open, and processed~~
−	~~- Open and processed vertexes are not added to the queue again~~
−
−	~~Time complexity of the algorithm O (\|V\| * (\|V\| + \|E\|)) = O((\|V\|)^2 + \|V * E\|)) = O(\|V * E\|)~~
−	~~- The number of edges does not grow slower than the number of vertexes~~
−	~~- In a graph of 1 vertex, when adding 1 vertex, 1+ edge is added~~
−	~~- In a complete graph of n vertices, the number of edges is determined by the Handshaking lemma~~
−	~~- - For a complete directed graph \|E\| = n * (n - 1) edges~~
−	~~- - For a complete not directed graph \|E\| = n * (n - 1) / 2 edges</pre>~~
−	~~--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 07:48, 30 June 2020 (UTC)~~

← Older revision		Revision as of 02:00, 14 July 2020
Line 1:		Line 1:
−	~~<pre>Algorithm:~~
−	~~BFS of each vertex v ∈ V, O(\|V\| * (\|V\| + \|E\|))~~
−	~~Saving adjacent vertexes to an adjacency matrix or adjacency list O(1)~~

−	~~Extensions:~~
−	~~BFS stops at a depth of 2~~
−	~~- Depth 1-adjacent v in the original graph~~
−	~~- Depth 2-adjacent v in the graph square~~
−	~~BFS uses the vertex statuses unopened, open, and processed~~
−	~~- Open and processed vertexes are not added to the queue again~~
−
−	~~Time complexity of the algorithm O (\|V\| * (\|V\| + \|E\|)) = O((\|V\|)^2 + \|V * E\|)) = O(\|V * E\|)~~
−	~~- The number of edges does not grow slower than the number of vertexes~~
−	~~- In a graph of 1 vertex, when adding 1 vertex, 1+ edge is added~~
−	~~- In a complete graph of n vertices, the number of edges is determined by the Handshaking lemma~~
−	~~- - For a complete directed graph \|E\| = n * (n - 1) edges~~
−	~~- - For a complete not directed graph \|E\| = n * (n - 1) / 2 edges</pre>~~
−	~~--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 07:48, 30 June 2020 (UTC)~~

← Older revision		Revision as of 07:48, 30 June 2020
Line 16:		Line 16:
	- - For a complete orgaf \|E\| = n * (n - 1) edges		- - For a complete orgaf \|E\| = n * (n - 1) edges
	- - For a complete neorgaph \|E\| = n * (n - 1) / 2 edges</pre>		- - For a complete neorgaph \|E\| = n * (n - 1) / 2 edges</pre>
		+	--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 07:48, 30 June 2020 (UTC)

← Older revision	Revision as of 12:09, 2 August 2020
Line 1:	Line 1:
	+	<pre>Algorithm:
	+	BFS of each vertex v ∈ V, O(\|V\| * (\|V\| + \|E\|))
	+	Saving adjacent vertexes to an adjacency matrix or adjacency list O(1)

	+	Extensions:
	+	BFS stops at a depth of 2
	+	- Depth 1-adjacent v in the original graph
	+	- Depth 2-adjacent v in the graph square
	+	BFS uses the vertex statuses unopened, open, and processed
	+	- Open and processed vertexes are not added to the queue again
	+
	+	Time complexity of the algorithm O (\|V\| * (\|V\| + \|E\|)) = O((\|V\|)^2 + \|V * E\|)) = O(\|V * E\|)
	+	- The number of edges does not grow slower than the number of vertexes
	+	- In a graph of 1 vertex, when adding 1 vertex, 1+ edge is added
	+	- In a complete graph of n vertices, the number of edges is determined by the Handshaking lemma
	+	- - For a complete directed graph \|E\| = n * (n - 1) edges
	+	- - For a complete not directed graph \|E\| = n * (n - 1) / 2 edges</pre>
	+	--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 07:48, 30 June 2020 (UTC)

← Older revision	Revision as of 08:14, 23 July 2020
Line 1:	Line 1:
	+	<pre>Algorithm:
	+	BFS of each vertex v ∈ V, O(\|V\| * (\|V\| + \|E\|))
	+	Saving adjacent vertexes to an adjacency matrix or adjacency list O(1)

	+	Extensions:
	+	BFS stops at a depth of 2
	+	- Depth 1-adjacent v in the original graph
	+	- Depth 2-adjacent v in the graph square
	+	BFS uses the vertex statuses unopened, open, and processed
	+	- Open and processed vertexes are not added to the queue again
	+
	+	Time complexity of the algorithm O (\|V\| * (\|V\| + \|E\|)) = O((\|V\|)^2 + \|V * E\|)) = O(\|V * E\|)
	+	- The number of edges does not grow slower than the number of vertexes
	+	- In a graph of 1 vertex, when adding 1 vertex, 1+ edge is added
	+	- In a complete graph of n vertices, the number of edges is determined by the Handshaking lemma
	+	- - For a complete directed graph \|E\| = n * (n - 1) edges
	+	- - For a complete not directed graph \|E\| = n * (n - 1) / 2 edges</pre>
	+	--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 07:48, 30 June 2020 (UTC)

← Older revision	Revision as of 11:21, 22 July 2020
Line 1:	Line 1:
	+	<pre>Algorithm:
	+	BFS of each vertex v ∈ V, O(\|V\| * (\|V\| + \|E\|))
	+	Saving adjacent vertexes to an adjacency matrix or adjacency list O(1)

	+	Extensions:
	+	BFS stops at a depth of 2
	+	- Depth 1-adjacent v in the original graph
	+	- Depth 2-adjacent v in the graph square
	+	BFS uses the vertex statuses unopened, open, and processed
	+	- Open and processed vertexes are not added to the queue again
	+
	+	Time complexity of the algorithm O (\|V\| * (\|V\| + \|E\|)) = O((\|V\|)^2 + \|V * E\|)) = O(\|V * E\|)
	+	- The number of edges does not grow slower than the number of vertexes
	+	- In a graph of 1 vertex, when adding 1 vertex, 1+ edge is added
	+	- In a complete graph of n vertices, the number of edges is determined by the Handshaking lemma
	+	- - For a complete directed graph \|E\| = n * (n - 1) edges
	+	- - For a complete not directed graph \|E\| = n * (n - 1) / 2 edges</pre>
	+	--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 07:48, 30 June 2020 (UTC)

@@ Line 5: / Line 5: @@
 Extensions:
 BFS stops at a depth of 2
-- Depth 1-adjacent v in the original orgaf
+- Depth 1-adjacent v in the original graph
-- Depth 2-adjacent v in the orgaf square
+- Depth 2-adjacent v in the graph square
 BFS uses the vertex statuses unopened, open, and processed
 - Open and processed vertexes are not added to the queue again
@@ Line 14: / Line 14: @@
 - In a graph of 1 vertex, when adding 1 vertex, 1+ edge is added
 - In a complete graph of n vertices, the number of edges is determined by the Handshaking lemma
-- - For a complete orgaf |E| = n * (n - 1) edges
+- - For a complete directed graph |E| = n * (n - 1) edges
-- - For a complete neorgaph |E| = n * (n - 1) / 2 edges</pre>
+- - For a complete not directed graph |E| = n * (n - 1) / 2 edges</pre>
 --[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 07:48, 30 June 2020 (UTC)