# Graphs Flashcards Preview

## Csc 225 > Graphs > Flashcards

Flashcards in Graphs Deck (22)
1
Q

Graph

A

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

2
Q

Undirected Edges

A
• 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
3
Q

Walk (undirected paths)

A

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

4
Q

Length (undirected paths)

A

Number of edges of a walk

If v1 =Vn closed otherwise open

5
Q

Trail (undirected paths)

A

No edge is repeated

6
Q

Circuit (undirected paths)

A

Is a closed trail

7
Q

Path (undirected paths)

A

No vertex is repeated

8
Q

Cycle (undirected paths)

A

A path with the same start and end vertices

9
Q

Connected graph

A

If every pair of vertices is connected by a path

10
Q

Simple graph

A

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

11
Q

Complete graph

A

Simple graph where an edge connects every pair of vertices

12
Q

Subgraph

A

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
13
Q

Spanning sub graph

A

Consists of all of the vertices of G

-2^m spanning subgraphs

14
Q

Tree (undirected)

A

And undirected graph such that:

• T is connected
• T has no cycle
15
Q

Forest

A

Is an u directed graph without cycles

-connected components of forests are trees

16
Q

Spanning tree

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

Spanning forest

A

Is a spanning sub graph that is a forest

18
Q

Directed Edges (arcs)

A

Represents an asymmetric relation between two vertices

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

Simple diagraph

A

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

20
Q

Connected digraph

A

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
21
Q

Directed Acyclic graph (DAGs)

A

Is a directed graph with no cycles

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

22
Q