commit a4b3bd67c4a0153513e4d230ac3fe174a93a57cd
parent f009e5af7ce9d7fcd4999cfdc2b16fadac96b6f6
Author: Andrew <andrewlaack1@gmail.com>
Date: Wed, 25 Sep 2024 08:53:08 -0500
Took notes
Diffstat:
17 files changed, 127 insertions(+), 19 deletions(-)
diff --git a/AdjacencyMatrix.md b/AdjacencyMatrix.md
@@ -0,0 +1,10 @@
+:data-structures: :cs:
+# Adjacency Matrix
+
+Ch 4
+
+## Notes
+
+**Definition:** An adjacency matrix is a matrix where each column represents a node as do the rows. In each position there is either a true or false denoting whether or not there is an edge between the two nodes.
+
+These matricies are symmetric about the main diagonal and the diagonal is all false as a node may not be connected to itself.
diff --git a/Algorithms.md b/Algorithms.md
@@ -38,21 +38,21 @@ Ch 3 (state analysis):
- [StirlingsFormula](StirlingsFormula.md)
Ch 4 (graphs):
- - Graph
- - Walk
- - Path
- - Cycle
- - Connected
- - Tree
- - AdjacencyMatrix (nxn matrix with true and false for a_i,j)
- - Digraph
- - Multigraph
- - Loop (different than cycle)
- - Sparse
- - IncidenceMatrix
- - Subgraph
- - ConnectedComponent
- - WeightedGraph
+ - [Graphs](Graphs.md)
+ - [Walk](Walk.md)
+ - [Path](Path.md)
+ - [Cycle](Cycle.md)
+ - [Connected](Connected.md)
+ - [Tree](Tree.md)
+ - [AdjacencyMatrix](AdjacencyMatrix.md) (nxn matrix with true and false for a_i,j)
+ - [Digraph](Digraph.md)
+ - [Multigraph](Multigraph.md)
+ - [Loop](Loop.md) (different than cycle)
+ - [Sparse](Sparse.md)
+ - [IncidenceMatrix](IncidenceMatrix.md)
+ - [Subgraph](Subgraph.md)
+ - [ConnectedComponent](ConnectedComponent.md)
+ - [WeightedGraph](WeightedGraph.md)
#### Intro To Algorithms (MIT)
diff --git a/Connected.md b/Connected.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Connected
+
+Ch 4
+
+## Notes
+
+**Definition:** Connected, in graph theory, means that there is a way to get from any node to any other node in the graph.
diff --git a/ConnectedComponent.md b/ConnectedComponent.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Connected Compoment
+
+Ch 4
+
+## Notes
+
+**Definition:** A connected component is a subgraph in which each component of the subgraph is conected.
diff --git a/Cycle.md b/Cycle.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Cycle
+
+Ch 4
+
+## Notes
+
+**Definition:** A cycle is a path with (when removing the last node) that starts and ends at the same node where the sequence is at least 3 long.
diff --git a/Digraph.md b/Digraph.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Digraph
+
+Ch 4
+
+## Notes
+
+**Definition:** A digraph is a directed graph meaning each edge has only one direction in which traversal is possible.
diff --git a/Graphs.md b/Graphs.md
@@ -10,6 +10,3 @@ Abstract Math 10.2.
**Cycle:** A cycle in a graph is a set of vertices such that traversal can be done back to itself.
Also see [[Tree.md]]
-
-
-
diff --git a/IncidenceMatrix.md b/IncidenceMatrix.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Incidence Matrix
+
+Ch 4
+
+## Notes
+
+**Definition:** An incidence matrix is another way to represent graphs where we maintain a linked list of all elements that are neighbors to x.
diff --git a/Loop.md b/Loop.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Loop
+
+Ch 4
+
+## Notes
+
+**Definition:** A loop in a graph is a connection to one's self.
diff --git a/Multigraph.md b/Multigraph.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Multi-Graph
+
+Ch 4
+
+## Notes
+
+**Definition:** A multi-graph is a graph that can contain multiple edges to the same node.
diff --git a/Path.md b/Path.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Path
+
+Ch 4
+
+## Notes
+
+**Definition:** A path is a sequence of adjacent nodes where nodes can not be repeated.
diff --git a/Sparse.md b/Sparse.md
@@ -0,0 +1,12 @@
+:data-structures: :cs:
+# Sparse
+
+Ch 4
+
+## Notes
+
+**Definition:** A sparse matrix is a matrix mostly containing zeroes.
+
+## Implementation
+
+It is sometimes useful to represent a sparse matrix as 3 arrays where the first defined the row, the second the column, and the third the value stored at the given location. This takes up less space and still keeps important information.
diff --git a/Subgraph.md b/Subgraph.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Subgraph
+
+Ch 4
+
+## Notes
+
+**Definition:** A subgraph of G(V,E) is a graph H(W,F) such that W is in V and F is in E.
diff --git a/Tree.md b/Tree.md
@@ -5,7 +5,7 @@ Abstract Math and CS202
## Notes
-**Definition:** Trees are graphs without cycles. Additionally, at least in cs, you can only have one root as a node can have no more than one parent.
+**Definition:** Trees are connected graphs without cycles.
There is no implication about split numbers or anything of the sort, but something interesting is that in all cases it must be true that the number of edges is one less than the number of vertices. This can be proved through [[StrongInduction.md]].
diff --git a/Walk.md b/Walk.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Walk
+
+Ch 4
+
+## Notes
+
+**Definition:** A walk is a sequence of adjacent nodes where each node can appear multiple times.
diff --git a/WeightedGraph.md b/WeightedGraph.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Weighted Graph
+
+Ch 4
+
+## Notes
+
+**Definition:** A weighted graph is a graph where we maintain a list of weights for edges to represent the cost of traversal.
diff --git a/index.md b/index.md
@@ -26,6 +26,7 @@ This is the index for my main note classifications. I will maintain this as a ho
[[Algorithms.md]]
[[Physics.md]]
[[Assembly.md]]
+[[Vocabulary.md]]
## Things to Learn More About
