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
