Graphs: Difference between revisions
From charlesreid1
No edit summary |
|||
| Line 12: | Line 12: | ||
* Definitions (graph, degree, path, cycle, connectivity, tree, forest, k-partite, contraction, Euler tours) | * Definitions (graph, degree, path, cycle, connectivity, tree, forest, k-partite, contraction, Euler tours) | ||
A graph G consist of a set of nodes (vertices) V and edges E | A '''graph''' G consist of a set of nodes (vertices) V and edges E, denoted <math>G(V,E)</math> | ||
Vertex set | '''Vertex set''' on graph G is denoted <math>V(G)</math> | ||
Edge set | '''Edge set''' on graph G is denoted <math>E(G)</math> | ||
Number of vertices in a graph is called the order and is denoted <math>|G|</math> | Number of vertices in a graph is called the '''order''' and is denoted <math>|G|</math> | ||
Number of edges in a graph is denoted <math>||G||</math> | Number of edges in a graph is denoted <math>||G||</math> | ||
Vertex v and edge e are incident if the edge connects to the vertex. | Vertex <math>v \in V</math> and edge <math>e \in E</math> are '''incident''' if the edge connects to the vertex. | ||
Set of all edges at a particular vertex v is denoted E(v) | Set of all edges at a particular vertex v is denoted <math>E(v)</math> | ||
Two vertices x, y are adjacent on a graph if there is an edge with endpoints x and y | Two vertices x, y are '''adjacent''' on a graph if there is an edge with endpoints x and y | ||
If all vertices are pairwise adjacent, the graph is complete | If all vertices are pairwise adjacent, the graph is '''complete''' | ||
For two graphs <math>G = (V,E)</math> and <math>G' = (V',E')</math>, the graphs are isomorphic if there exists a biijection from G to G'. | For two graphs <math>G = (V,E)</math> and <math>G' = (V',E')</math>, the graphs are isomorphic if there exists a biijection from G to G'. | ||
| Line 34: | Line 34: | ||
If we have two graphs G and G', we say that G' is a subgraph of G if all V' subset of V and all E' subset of E | If we have two graphs G and G', we say that G' is a subgraph of G if all V' subset of V and all E' subset of E | ||
A subgraph G' is a spanning subgraph of G if all V' span all of G (if V' = V) | A subgraph G' is a '''spanning subgraph''' of G if all V' span all of G (if V' = V) | ||
===Chapter 2: Matching=== | ===Chapter 2: Matching=== | ||
Revision as of 04:01, 14 August 2017
Graphs are mathematical objects consisting of nodes and edges. The original inventor of graph theory was Leonhard Euler, who used it to solve the Seven Bridges of Königsberg problem.
Notes
Diestel - Graph Theory
Link: http://www.cs.unibo.it/babaoglu/courses/cas00-01/tutorials/GraphTheory.pdf
Chapter 1: Basics
Outline:
- Definitions (graph, degree, path, cycle, connectivity, tree, forest, k-partite, contraction, Euler tours)
A graph G consist of a set of nodes (vertices) V and edges E, denoted $ G(V,E) $
Vertex set on graph G is denoted $ V(G) $
Edge set on graph G is denoted $ E(G) $
Number of vertices in a graph is called the order and is denoted $ |G| $
Number of edges in a graph is denoted $ ||G|| $
Vertex $ v \in V $ and edge $ e \in E $ are incident if the edge connects to the vertex.
Set of all edges at a particular vertex v is denoted $ E(v) $
Two vertices x, y are adjacent on a graph if there is an edge with endpoints x and y
If all vertices are pairwise adjacent, the graph is complete
For two graphs $ G = (V,E) $ and $ G' = (V',E') $, the graphs are isomorphic if there exists a biijection from G to G'.
If we have two graphs G and G', we say that G' is a subgraph of G if all V' subset of V and all E' subset of E
A subgraph G' is a spanning subgraph of G if all V' span all of G (if V' = V)
Chapter 2: Matching
Bipartite graph matching
k-partite graph matching
Chapter 3: Connectivity
2-connected graphs
3-connected graphs
Menger's Theorem
Mader's Theorem
Spanning trees (and edge-disjoint spanning trees)
Chapter 4: Planar Graphs
Topology
Plane graphs
Algebraic criteria
Chapter 5: Coloring
Coloring vertices
Coloring edges
Chapter 6: Flows
Circulations
Flows in networks
k-flows
Flow coloring
Tutte's flow conjectures
Chapter 7 and 8: Substructures
Subgraphs
Regularity lemma
Hadwigen's theorem