ITA - Week 6 Flashcards
What is an undirected graph
A pair G = (Vertices, Edges)
Each edge is an unordered pair of vertices
What is a simple graph
At most a single edge between two vertices and no self loops
What is a multigraph
Allows more than one edge between two vertices (can have infinite edges)
What is a complete graph
A graph with every pair of its vertices connected by an edge (all possible edges)
What are adjacent vertices
Neighbouring vertices
How many edges will a complete graph of n vertices have
N choose 2
What is an adjacency-list
A graph represented in a list which stores information about which vertex is adjacent to another vertex using a linked list
What is a linked list
A linked list is a list of elements (nodes) connected together like a chain
What do nodes contain
A Data field - Data about the element
A Next field - A pointer to link the node to another
Why is a linked list useful
It can be used to implement a queue and stack
What is the queue (FIFO) data structure
Elements are added (enqueue) to the tail
Elements are removed (dequeue) from the head
What does FIFO stand for
First in first out
Advantage of linked list over array
Elements can be added and removed without reorganising the entire data structure
What is a stack (LIFO) data structure
A data structure in which we add (push) elements to the head and remove (pop) elements from the head
What does LIFO stand for
Last In First Out
What is the indegree of a vertex vs the outdegree
The number of edges leading into the vertex vs The number of edges leading away from the vertex
What is an adjacency matrix
An n x n matrix where the element at row i and column j is a 1 if there is an edge from vertex i to j, otherwise it is 0
Adjacency matrices undirected vs directed number of elements
Undirected: n(n-1)/2
Directed: n(n-1)
What is a sparse graph
Few edges- Adjacency lists use less space
Dense graph - Adjacency matrices use less space
What makes a simple path
If all vertices in the path are distinct
Path definition
Between vertex u and v in a graph is a sequence of edges (u,x1), (x1, x2),…(xn-1, v)
Euler cycle definition
An euler cycle in a graph G is a cycle visiting every edge exactly once
What makes a cycle euler
If the degree of all nodes are even
When is a graph called a tree
If the graph is connected and acyclic
When is a graph called a forest
When the graph has no cycles but isn’t necessarily connected
What is the root of the tree
The topmost vertex
What is the degree of a tree
The maximum degree of all vertices
