Graphs Flashcards
What is V in the graph G = (V, E)
a nonempty set of vertices (nodes)
What is E in the graph G = (V, E)
a set of edges.
What is a simple graph?
A graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices.
In a simple graph if there is an edge associated with {u,v}, {u,v} is an edge
What is a directed graph?
Also called digraph, (V,E) consists of nonempty set of vertices V and a set of directed edges (arcs) E. Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u,v) is said to start at u and end at v.
What is multiplicity
the number of directed edges associated to an ordered pair of vertices
What is adjacent?
Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge e of G.
What is incident
An edge e is incident with two adjacent vertices
What is the neighborhood?
The neighborhood of a vertex of graph G(V,E) is the set of all neighbors of v.
Denoted N(v)
If A is a subset of V, we denote by N(A) the set of all vertices in G that are adjacent to at least one vertex in A.
What is the degree?
Degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by deg(v)
What is isolated?
When a degree of a vertex is zero
What is pendant?
If a vertex has exactly degree one
What is the handshaking theorem?
In a graph G = (V,E) an undirected graph with m edges,
the sum of all degrees of all vertices equal two times the number of edges.
An undirected graph has an even number of vertices of odd degree
What is in-degree and out-degree?
in-degree (deg-(v) ) is the number of edges with v as their terminal vertex.
the out-degree of v is the number of edges with v as their initial vertex.
A loop contributes 1 to both the in-degree and out-degree
What is theorem 3?
a graph with directed edges
The sum of all in-degrees of the vertices is equal to the number of edges, which is also equal to the number of out-degree
