Graphs

Question 1

Graph

Answer 1

G =(V,E) is a set V of vertices(nodes) and a collection E of pairs from V, called edges(arcs)

Question 2

Undirected Edges

Answer 2

• represents a symmetric relation between two vertices
• degree of vertex is number of incident edges
• parallel edges: not that one edge between two vertices
• self-loop: edge connects vertex to itself

Question 3

Walk (undirected paths)

Answer 3

Is sequence of vertices v1,v2, … , Vn such that there exists edges {v1,v2}, {v2,v3}, … {Vn-1, Vn}

Question 4

Length (undirected paths)

Answer 4

Number of edges of a walk

If v1 =Vn closed otherwise open

Question 5

Trail (undirected paths)

Answer 5

No edge is repeated

Question 6

Circuit (undirected paths)

Answer 6

Is a closed trail

Question 7

Path (undirected paths)

Answer 7

No vertex is repeated

Question 8

Cycle (undirected paths)

Answer 8

A path with the same start and end vertices

Question 9

Connected graph

Answer 9

If every pair of vertices is connected by a path

Question 10

Simple graph

Answer 10

Is a graph with no self-loops and no parallel or multi-edges

Question 11

Complete graph

Answer 11

Simple graph where an edge connects every pair of vertices

Question 12

Subgraph

Answer 12

Sub graph of G if

• new V is a subset of V
• new E consists of edges {v,w} in E such that both v and w are in new V

Question 13

Spanning sub graph

Answer 13

Consists of all of the vertices of G

-2^m spanning subgraphs

Question 14

Tree (undirected)

Answer 14

And undirected graph such that:

• T is connected
• T has no cycle

Question 15

Forest

Answer 15

Is an u directed graph without cycles

-connected components of forests are trees

Question 16

Spanning tree

Answer 16

• of a connected graph is a spanning sub graph that is a tree
• is not unique unless the graph is a tree

Question 17

Spanning forest

Answer 17

Is a spanning sub graph that is a forest

Question 18

Directed Edges (arcs)

Answer 18

Represents an asymmetric relation between two vertices

• arc goes from source to destination
• indegree: number of incoming arcs
• outdegree: number of outgoing arcs

Question 19

Simple diagraph

Answer 19

Is a graph with no self-loops and no parallel or multi-edges
-has O(n^2) edges

Question 20

Connected digraph

Answer 20

Given vertices u and v we say v is reachable from u if there is a directed path from u to v

• connected if every pair of vertices is connected by an undirected path
• strongly connected if for every pair of vertices u and v, u is reachable from v and vis versa

Question 21

Directed Acyclic graph (DAGs)

Answer 21

Is a directed graph with no cycles

-more general then trees, but less general that arbitrary directed graphs

Question 22

Graph ADTs

Answer 22

• Edge list structure
• adjacency list structure
• adjacency-matrix structure