Week 7 Flashcards
What is connectivity information?
- Defined by many kinds of relationships that exist between pairs of objects such as city maps, where edges are roads and cities are nodes
- graphs are one way in which connectivity information can be stored, expressed and utilised
What are graphs?
- a set of vertices connected by edges
Edges can be directed or undirected: - an edge (u,v) is directed from u to v if the pair (u,v) is ordered
- an edge {u,v} is undirected if {u,v} is unordered
- if all edges of a graph are directed, we refer to it as a digraph
Define adjacent, incident edge, outgoing edge, incoming edge and degree in regards to graphs
- two vertices are adjacent if they are endpoints of the same edge
- an edge is incident to a vertex if it is one of the endpoints of the edge
- the vertex of an outgoing edge is the vertex the directed edge originates from
- the vertex of an incoming edge is the directed edge whose destination is that vertex
- the degree of a vertex is equal to the number of it’s incident edges
What are the formula’s for the number of edges in a directed and undirected graph?
- directed = indeg(v) + outdeg(v) = m
What is a simple graph?
- an undirected graph that has at most one edge between each pair of vertices
- a directed graph is simple if there is at most one directed edge from u to v for every pair of distinct vertices u and v (so an arrow in each direction between (u,v) would count as simple)
What is the sum of the max number of edges a simple directed/undirected graph should have?
for a graph G of n vertices and m edges:
- undirected: m = n(n-1)/2 to remove repeated connections
- directed: m <= n(n-1)
What is a walk, path, circuit, cycle and directed walk in regards to graphs?
- A walk is an alternating sequence of vertices and edges in a graph
- A path is a walk where every vertex in the walk is distinct
- A circuit is a walk where the start and end vertex are the same
- a cycle is a circuit where every vertex in the cycle is distinct
- a directed walk is a walk in which every edge is directed and we traverse the edges along their direction.
- a directed path, circuit and cycle are similarly defined to a directed walk
What is a subgraph, spanning subgraph, connected graph and not connected graph in regards to graphs?
- a subgraph of graph G is a graph H whose vertices and edges are subsets of the vertices and edges of G
- a spanning subgraph of G is a subgraph that contains all the vertices of G (all the same nodes)
- a connected graph is a graph where for any two distinct vertices there is a path between them
What is a forest, a tree and a tree with a rooted tree and spanning tree?
- a forest is a graph with no cycles
- a tree is a connected forest (a connected graph with no cycles)
- a rooted tree is a tree with a distinguished root node (otherwise unrooted trees are known as free trees)
- a spanning tree is a spanning subgraph that is a free tree
What are the 4 facts that hold for Graphs?
- n nodes, m edges, m = n - 1 if G is a tree
- If G has m >= n edges, G has a cycle
- If G has no cycle m <= n-1
- If G is connected then m >= n-1
What are two methods we can use to represent graphs?
- Adjacency matrix, adjacency lists
What is an adjacency list?
- a method for storing graphs in memory
- lists all nodes of the graph and for each node it stores its neighbours via linked lists
- good for representing sparse graphs as they don’t have many edges compared to number of vertices as it wastes less memory
- had time complexity O(n + m)
What is an adjacency matrix?
- a method for storing graphs in memory
- stores a matrix with every node along each axis
- 0 represents no edge, 1 represents an edge
- for an undirected graph the matrix will be symmetric
- O(n) to access all elements
- more efficient for storing densely populated graphs (graphs with many edges)
Digraphs, reachability
- a digraph is a graph with all directed edges
- give two vertices in a diagraph, we say u reaches v if u has a directed path to v
- a digraph is strongly connected if for every pair of vertices (u,v), u reaches v and v reaches u
- a digraph is acyclic if it contains for directed cycles
What are the two common graph searching methods?
BFS and DFS
- BFS explores layer by layer, visiting all the neighbours/adjacent nodes of a node before progressing to the next layer/node, it does this until all nodes have been visited
- DFS progresses as far down one route/path and then backtracks and goes as far down the next path as it can, it does this until all nodes are visited
What do we use to realise an implementation of BFS and DFS
- BFS is implemented with a queue
- DFS is implemented by a stack
What is a weighted graph
Graphs can have weights (numerical values) along their edges or vertices, representing the cost perhaps of visiting/traversing them
What is single source shortest paths problem?
- for some vertex v, find the shortest path from v to every other node in the graph
- the shortest path is the sum of all the weights of the edges in the path
- Dijkstra’s algorithm is the Greedy Method solution to this problem
What is Dijkstra’s algorithm?
- Solution for finding the shortest path from a vertex v to every other node in the graph
- We assume all the weights of the edges are non- negative
What is edge relaxation
- if we find a better path from one node to the source node, we replace it
- so we check if the direct distance of v to z can be reduced by going via vertex u
What is the running time of Dijkstra’s algorithm?
O((n+m)logn)
