7 | Data structures / graphs Flashcards

Question

List implemented with use of pointers and records?

Answer 1

List can be implemented with use of pointers and records (for the nodes) type list = ↑ node type node = record value:integer next: ↑ node Each node, except the last, points to its successor The last has a value nil

Answer 2

type list = record counter: 0 . . 𝑚𝑎𝑥𝑙𝑒𝑛𝑔𝑡ℎ value: array [1. . maxlength] of integers --> in constant time ---------------------------------------- type list = ↑ node type node = record value:integer next: ↑ node In time 𝑂(𝑘) , due to the following of pointers

Answer 3

type list = record counter: 0 . . 𝑚𝑎𝑥𝑙𝑒𝑛𝑔𝑡ℎ value: array [1. . maxlength] of integers --> yes ---------------------------------------- type list = ↑ node type node = record value:integer next: ↑ node --> No, it can grow and shrink dynamically

Answer 4

Inserting an item after the k-th item type list = record counter: 0 . . 𝑚𝑎𝑥𝑙𝑒𝑛𝑔𝑡ℎ value: array [1. . maxlength] of integers --> in time Θ 𝑛 type list = ↑ node type node = record value:integer next: ↑ node --> In time 𝑂(1) , by copying and changing few fields

Answer 5

With nodes, pointers: we gained dynamic memory allocation Accessing: but we lost efficiency of accessing an element of a list: we need to traverse list to find the kth element Insertion: much easier to insert a new element after kth element - only two operations - constant time operation

Answer 6

Informal: a graph (𝐺) is an abstract representation of a set of components (nodes/vertices) where some pairs of the components are connected by links (edges).

Answer 7

A graph is a pair 𝐺 = (𝑉, 𝐸) , such that 𝐸 ⊆ {{𝑢, 𝑣}|𝑢, 𝑣 ∈ 𝑉}. We refer to 𝑉 as a set of nodes (or vertices) and 𝐸 as a set of edges.

Answer 8

are incident with

Answer 9

is incident with connects (only different types can be incident!)

Answer 10

adjacent neighbours (only same type can be adjacent!)

Answer 11

𝑛 = |𝑉(𝐺)|

Answer 12

𝑚 = |𝐸(𝐺)|

Answer 13

A graph is called simple, if it does not contain multi-edges or loops. Otherwise it is called a multi-graph

Answer 14

Two edges 𝑒 and 𝑓 are called parallel, if they connect the same vertices. Parallel edges form a multi-edge.

Answer 15

If an edge connects a vertex to itself (i.e. 𝑒 = {𝑣, 𝑣}) it is called a loop.

Answer 16

(A directed graph is a pair 𝐺 = 𝑉, 𝐸 , such that 𝐸 ⊆ {(𝑢, 𝑣)|𝑢, 𝑣 ∈ 𝑉}. We refer to 𝑉 as a set of nodes (or vertices) and 𝐸 as a set of directed edges.) __For the edge 𝑒 = (𝑢, 𝑣), 𝑢 is the head and 𝑣 is the tail__

Answer 17

A weighted directed graph is a pair 𝐺 = 𝑉, 𝐸 , such that 𝐸 ⊆ {(𝑢, 𝑣)|𝑢, 𝑣 ∈ 𝑉}, with a weight function 𝑤: 𝐸 → ℝ. weight = distance, resource availability / capacity

Answer 18

Three ways: Adjacency matrix incidence matrix or adjacency list

Answer 19

𝐴[𝑢, 𝑣] = 1 𝑖𝑓 (𝑢, 𝑣) ∈ 𝐸(𝐺) 𝐴[𝑢, 𝑣] = 0 𝑖𝑓 (𝑢, 𝑣) ∉ 𝐸(𝐺) Constant time to check for presence of an edge between two nodes Edge weights can be considered (instead of 1). Adjacency matrix of an undirected graph is symmetric

Answer 20

𝐴[𝑢, 𝑣] = 1 𝑖𝑓 (𝑢, 𝑣) ∈ 𝐸(𝐺) 𝐴[𝑢, 𝑣] = 0 𝑖𝑓 (𝑢, 𝑣) ∉ 𝐸(𝐺) Adjacency matrix of an undirected graph may not be symmetrical

Answer 21

𝐴[𝑢,𝑒] = 1 𝑖𝑓 𝑢 ∈ 𝑒 𝐴[𝑢,𝑒] = 0 𝑖𝑓 𝑢 ∉ 𝑒 Edge weights can be considered (instead of 1).

Answer 22

𝐴[𝑢,𝑒] = −1 𝑖𝑓𝑒 = (𝑢, 𝑣) 𝐴[𝑢,𝑒] = 1 𝑖𝑓 𝑒 = (𝑣, 𝑢) 𝐴[𝑢,𝑒] = 0, 𝑢 ∉ 𝑒

Answer 23

between different types node - edge (incidence matrix allows you to represent more relationships eg stoichiometric matrices in CMCN)

Answer 24

between same type eg node - node edge - edge

Answer 25

advantages: - constant time to determine whether there is an edge between two nodes - can directly see what neighbours are disadvantages - not dynamically changeable

Answer 26

- you have to traverse through list in order to find a node in the list - dynamic changes allowed - Space required is quadratic in the number of nodes - For sparse graphs (number of edges which grows linearly with the number of edges), list representation is space efficient - Look-up of neighbours in constant time, but checking all neighbours requires investigation of an entire row - All neighbours can be investigated in time smaller than 𝑛, but looking up neighbours is not in constant time

Answer 27

a pair 𝐺 = (𝑉, 𝐸), such that 𝐸 ⊆ (𝑆,𝑄) , 𝑆,𝑄 ∈ 𝒫(𝑉), with a weight function 𝑤_𝑆: 𝑆 → ℝ weight = resource demand / production eg 𝑉 = {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5} 𝑤({𝑣1, 𝑣6}) = {−1, −2} 𝑤({𝑣4, 𝑣7}) = {1,1}

Answer 28

incidence matrix (eg stoichiometric matrix in CMCN)

Answer 29

Let 𝐺 = (𝑉, 𝐸) be a simple graph. A sequence 𝑊 = (𝑣₁, 𝑒₁, 𝑣₂, … 𝑒_𝑘−1, 𝑣_𝑘) with 𝑣_𝑖 ∈ 𝑉(𝐺) , 1 ≤ 𝑖 ≤ 𝑘 and 𝑒_𝑖 = 𝑣_𝑖, 𝑣_𝑖+1 ∈ 𝐸(𝐺) , 1 ≤ 𝑖 ≤ 𝑘 − 1 is called a walk. A walk is closed if 𝑣₁ = 𝑣_𝑘

Answer 30

Yes (in a path they cannot)

Answer 31

Let 𝐺 = (𝑉, 𝐸) be a simple graph. A walk 𝑊 = (𝑣₁, 𝑒₁, 𝑣₂, … 𝑒_𝑘−1, 𝑣_𝑘) is a path if 𝑣_𝑖 ≠ 𝑣_j, 1 ≤ 𝑖, j ≤ 𝑘, i ≠ j A path is a cycle if 𝑣₁ = 𝑣_𝑘

Answer 32

No (except in a cycle - then first/last is the same) If repetition --> a path but not a walk

Answer 33

minimal refers to subgraphs (or subsets) minimum refers to cardinality (number of nodes/edges) A subgraph 𝐻 of 𝐺 is minimal with respect to a property 𝑃 if 𝐻 satisfies 𝑃 and there exists no strict subgraph 𝐻′ of 𝐻 that also satisfies 𝑃. (Analogously: maximal vs. maximum)

Answer 34

check if removal of any object from the structure breaks the property in question --> if so then it is minimal

Answer 35

Let 𝐺 = (𝑉, 𝐸) be a graph. Let 𝐺 is connected if for every two nodes there exists a path between any two nodes 𝑢 and 𝑣 in 𝐺 Connected component is a maximal connected subgraph

Answer 36

re connectedness: connected component is a maximal connected subgraph. (relevant for minimum spanning trees)

Answer 37

A graph 𝐺 is a tree if it is connected and has no cycles. Hence, a connected forest is a tree.

Answer 38

A graph 𝐺 is a forest if it has no cycles. Hence, a connected forest is a tree.

Answer 39

A tree is called a rooted tree if one vertex has been designated the root.

Answer 40

- the parent of a vertex is the vertex connected to it on the path to the root, - every vertex except the root has a unique parent, - a child of a vertex v is a vertex of which v is the parent

Answer 41

- a leaf is a vertex without children - a node that is not a leaf is call internal - Node u is an ancestor of v if it lies on the path from the root to v

Answer 42

Two ways (↑ = a pointer) ``` type treenode1 = record value: 𝑖𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 eldestchild: ↑ treenode 1 next-sibling: ↑ treenode 1 ``` ``` type treenode2 = record value: 𝑖𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 parent: ↑ treenode 2 ```

Answer 43

1: All nodes can be represented with the same record Many operations are inefficient (e.g. finding a parent of a node) 2: Very economical representation Many operations are inefficient, unless they are applied to a node always going up the rooted tree

Answer 44

``` type binary-node = record value: 𝑖𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 left-child: ↑ binary-node right-child: ↑ binary-node ``` ``` type k-ary-node = record value: 𝑖𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 child: array [1. . 𝑘] 𝑜𝑓 ↑ 𝑘-𝑎𝑟𝑦-node ```

Answer 45

A binary tree where value contained in every internal node is both: - greater than or equal to value in left child or any of child‘s descendants - smaller than or equal to the value in the right child or any of the child‘s descendants

Answer 46

``` function search(x,r) if r = nil then return nil #{x is not in the tree} else if x = r ↑.value then return r else if x < r ↑.value then return search(x, r ↑.left-child) else return search(x, r ↑.right-child) ```

Answer 47

Height of it's root

Answer 48

- Height of a node: number of edges in the longest path from the node to a leaf - Depth of a node: number of edges in the path from the root to the node - Level of a node: height of the root – depth of the nodes

Answer 49

Zoran: parent of only one child (online: Only child of its parent)

Answer 50

Binary tree is essentialy complete if: - each internal node has exactly two children (possible exception of one special node) - If there is a special node: situated on level 1, has a left but no right child - Either all leaves are on level 0, or else they are on levels 0 and 1, and no leaf on level 1 is to the left of an internal node at the same level

Answer 51

Heap - special type of a rooted tree - essentially complete binary tree such that value of any internal node is greater than or equal to the values of its children - can be implemented efficiently with an array, without any explicit pointers

Answer 52

- 2^𝑘−𝑖 nodes on level 𝑖, 1 ≤ 𝑖 ≤ 𝑘 - at most 2^𝑘 nodes on level 0

Answer 53

2^𝑘 ≤ 𝑛 < 2^𝑘+1 Therefore, 𝑘 ≤ log₂𝑛 < 𝑘 + 1, i.e. 𝑘 = ⌊log₂𝑛⌋