W11 - graph theory 1 Flashcards
(12 cards)
What does Adjacency mean
two vertices v,w of a graph are adjacent if v,w is an edge in the graph
notation v~w or v,w∈E
If v and w are adjacent, then they are said to be endpoints, or endvertices, of the edge v,w between them
Incidence meainng
Vertex-edge incidence: if that vertex is one of the endpoints of the edge.
Edge-edge incidence: Two edges are incident if they share the same vertex
isolated vertex meaning
A vertex is isolated if it does not belong to (i.e., is not incident with) any edges.
deg(v)=0
Leaf vertex meaning
A vertex is a leaf if it belongs to exactly one edge.
deg(v)=1
Special type of graphs and their notation
Complete, path, cycle graphs
Complete graph
- every pair of vertices joined by an edge
K_n
Path graph
* Has n vertities and n−1 edges where the vertices can be put in a sequence so that two vertices are adjacent if and only if they are consecutive in the sequence
* P_(n-1)
Cycle
* Has n vertities and n edges and can be formed from a path graph on the same vertices by adding a new edge between the first and last vertex of the path
* C_n
Handshaking Lemma
sum of (deg(v)) =?
and one of the corollaries
sum of all deg(v) = 2*m
Every graph has an even number of vertices of odd degree. The number of odd-degree vertices is even
m=number of edges
n= number of nodes
Average degree of G
what is the formula?
comes from handshaking lemma
Average degree of G= (2*m/n)
m=number of edges
n= number of nodes
What is a walk, trail, path and cycle?
Properties of repeated edges and repeated vertices
Walk
* Closed walk: start=end
* Repeated edges allowed
* Repeated Vertices allowed
Trails
* closed trail: start=end
* No repeated edges
* repeated vertices allowed
Paths
* No repeated edges
* No repeated vertices
Cycles
* Start=end
* No repeated edges
* No repeated vertices (apart from start and end)
What does it mean for a graph to be connected?
A graph G is connected if for every pair of vertices v and w, there is a path from v to w in G.
What is a component of a graph
A component of a graph is a connected subgraph of a graph which is not contained in any larger connected subgraph of that graph
* Maximal (you cannot add any more vertices or edges from the original graph while maintaining connectivity)
Bipartite graph meaning
A graph is bipartite:
* iff it has 2 coloring, OR
* iff it has no odd closed walk
What is an Euler tours
Also, which graph have euler tours
A closed trail that uses every edge.
* Trail = every edge gets used exactly once
* Closed = finishes at starting vertex
A graph has an Euler tour iff every vertex has an even degree
