ITA - Week 6

Question 1

What is an undirected graph

Answer 1

A pair G = (Vertices, Edges)

Each edge is an unordered pair of vertices

Question 2

What is a simple graph

Answer 2

At most a single edge between two vertices and no self loops

Question 3

What is a multigraph

Answer 3

Allows more than one edge between two vertices (can have infinite edges)

Question 4

What is a complete graph

Answer 4

A graph with every pair of its vertices connected by an edge (all possible edges)

Question 5

What are adjacent vertices

Answer 5

Neighbouring vertices

Question 6

How many edges will a complete graph of n vertices have

Answer 6

N choose 2

Question 7

What is an adjacency-list

Answer 7

A graph represented in a list which stores information about which vertex is adjacent to another vertex using a linked list

Question 8

What is a linked list

Answer 8

A linked list is a list of elements (nodes) connected together like a chain

Question 9

What do nodes contain

Answer 9

A Data field - Data about the element

A Next field - A pointer to link the node to another

Question 10

Why is a linked list useful

Answer 10

It can be used to implement a queue and stack

Question 11

What is the queue (FIFO) data structure

Answer 11

Elements are added (enqueue) to the tail

Elements are removed (dequeue) from the head

Question 12

What does FIFO stand for

Answer 12

First in first out

Question 13

Advantage of linked list over array

Answer 13

Elements can be added and removed without reorganising the entire data structure

Question 14

What is a stack (LIFO) data structure

Answer 14

A data structure in which we add (push) elements to the head and remove (pop) elements from the head

Question 15

What does LIFO stand for

Answer 15

Last In First Out

Question 16

What is the indegree of a vertex vs the outdegree

Answer 16

The number of edges leading into the vertex vs The number of edges leading away from the vertex

Question 17

What is an adjacency matrix

Answer 17

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

Question 18

Adjacency matrices undirected vs directed number of elements

Answer 18

Undirected: n(n-1)/2
Directed: n(n-1)

Question 19

What is a sparse graph

Answer 19

Few edges- Adjacency lists use less space

Dense graph - Adjacency matrices use less space

Question 20

What makes a simple path

Answer 20

If all vertices in the path are distinct

Question 21

Path definition

Answer 21

Between vertex u and v in a graph is a sequence of edges (u,x1), (x1, x2),…(xn-1, v)

Question 22

Euler cycle definition

Answer 22

An euler cycle in a graph G is a cycle visiting every edge exactly once

Question 23

What makes a cycle euler

Answer 23

If the degree of all nodes are even

Question 24

When is a graph called a tree

Answer 24

If the graph is connected and acyclic

Question 25

When is a graph called a forest

Answer 25

When the graph has no cycles but isn’t necessarily connected

Question 26

What is the root of the tree

Answer 26

The topmost vertex

Question 27

What is the degree of a tree

Answer 27

The maximum degree of all vertices