Graph Theory Flashcards
What is an abstract map?
Shows the connections but not the geographical positions.
What is a graph?
Consists of a set of nodes/vertices + set of edges. An edge connects 2 nodes + represents some relationship between them. An edge can be weighted/labelled to give them more info (e.g. distance between node). Doesn’t have to be an edge between every pairs of nodes, graph doesn’t have to be fully connected.
What is the total weight of a tour of a graph?
(Travelling node to node) Sum of all edges used. Finding tour with min total weight is the Travelling Salesman problem. Edges of graphs don’t have to have weights. Edges of a graph can have a direction. Unless stated otherwise, we will use undirected, unlabelled graphs. The positions of nodes aren’t significant, if they have the same num of nodes with same names & matching edges, they’re the same graph.
How can we represent edges?
A node can be defined as a set of labels.
Use a matrix when rows + columns both indicate nodes. At each intersection, store “1” if there’s an edge and 0 otherwise. Each edge in a directed graph is a pair, not a set. If the graph is directed, the matrix may not be symmetrical.
How do we express the degree of a node in an undirected graph?
Links (N) = {e ∈ Edges ∙ N ∈ e}. i.e. The number of edges meeting a node N. card ({{e ∈ Edges ∙ N ∈ e}.
What is a path in a graph?
Sequence of nodes such that there’s an edge of the graph between any 2 consecutive nodes in the sequence. (len(p)>1)^(∀i∈{1,…,len(p)-1}∙{p(i),p(i+1)}∈Edges)
What is Euler’s Theorem?
Showed that a certain problem couldn’t be done. We think about nodes of an even and odd degree. If we have 0 odd nodes, a path can be found starting at any node and finishing at the starting node. If we have 1, there is no path crossing each edge exactly once. If we have 2, a path can be found starting at node of odd degree and finishing at the other. If we have more than 2, there is no path crossing each edge exactly once. To count odd degree nodes, Degree (n) = card(Links(n)). O = card ({n|n∈Nodes∙Degree(n) mod 2 = 1}).
When is a graph fully connected?
Between every pair of nodes, there is an edge. To find the total number of edges, we use sigma from I = 1 to n – 1 with the equation((N-1)N)/2. Can also just use ((N-1)N)/2.
What is a cycle?
Path which starts and ends at same node, has at least 3 edges, doesn’t cross same edge twice + doesn’t visit any node twice, except for start/end node. A graph with no cycles is acyclic. A connected graph is one in which for every 2 nodes in it, it’s possible to find a path between them. A tree is a connected, acyclic graph.
How do we build a binary search tree?
To build a binary search tree, sort sequence, root value is median, repeat with values less than it, repeat with values more than it.
