Karteikarten
graph theory
Karten in diesem Stapel (66)
- 1graphG consists of finite sets V and E
- 2vertex set V(G)set of vertices of G
- 3edge set E(G)set of edges of a graph OR set of unordered pairs of vertices
- 4directed graph / digrapha graph where set E is an ordered set of vertices
- 5multigrapha graph where repeated elements are allowed in E
- 6pseudographa graph where edges are allowed to connect a vertex to itself; loops
- 7hypergrapha graph where instead of edges, we consider subsets of vertices
- 8edge notation{u,v} = uv
- 9ordercardinality of vertex set
- 10sizecardinality of edge set
- 11adjacentu and v are adjacent if uv belongs to E
- 12nonadjacentu,v non adjacent of uv doesn't belong to E
- 13end verticesend vertices of edge uv are u, v
- 14incidentv is incident with an edge e if v is an edge vertex of e
- 15open neighborhood of vN(v) = {x in V| vx in E}
all the vertices adjacent to v, not including v - 16closed neighborhood of VN[v] = N(v) U v
- 17open, closed neighborhoods of set of vertices Sopen neighborhood: union of N(v) for all v in S
closed neighborhood: union of N[v] for all v in S - 18degree of Vdeg(v) = number of incident edges with v
- 19max, min degreemax degree: Delta(G) = max{deg(v) | v in V(G)}
min degree: delta(G) = min{deg(v)| v in V(G)} - 20degree sequence of graph of order nan n-term sequence of vertex degrees, usually written in descending order
- 21thm: edges and degrees relationshipsum of all degrees = 2(#edges)
- 22thm: number of vertices of odd degreeALWAYS even
- 23walkany sequence of vertices (not necessarily distinct) v1,...,vk where v(i)v(i+1) is an edge
AKA v1-vk walk - 24pathwalk where vertices in walk are distinct
path - hopscotch, picking vertices
- 25trailedges in walk are distinct
trail - trailing along / dragging along
- 26closed path / cyclepath v1,...,vk together with the edge vk,v1
cycle path sounds like psychopath
- 27closed trail / circuita trail that begins and ends at the same vertex
circuit - has a t, related to trail - 28length of walk, trail, circuit, cyclenumber of edges counting repetitions
- 29thm: walks and pathsin G with vertices u, v every u-v walk contains a u-v path
- 30vertex deletionG-v: remove v and all incident edges
- 31edge deletionG-E: remove edge, but not vertices
- 32connectedevery pair of vertices can be joined by a path. informally, can pick up the graph in one piece
- 33connected componenta maximally connected piece of a graph
- 34cut vertexa vertex where deleting it from G causes the number of components to increase
- 35bridgean edge e is a bridge if G-e has more components than G
- 36vertex cut seta vertex cut set is a strict subset S of V(G) where G-S is disconnected
- 37complete grapheach vertex in a graph is adjacent to every other vertex
K_n, n denotes order of the graph
- 38connectivity of GK(G) - minimum size of a cut set of G
- 39k-connecteda graph if k-connected if k<= K(G)
- 40thm: connectivity and K(G)a graph is connected IF AND ONLY IF K(G) >=1
- 41thm: K(G) and lacking cut verticesK(G) >= 2 IF AND ONLY IF G is connected and has no cut vertices
- 42thm: 2-connected graph and cycleevery 2-connected graph contains at least 1 cycle
- 43thm: K(G) and delta(G)for all graphs, K(G) <= delta(G)
- 44empty graphE_n is an empty graph on n vertices if the graph is order n, but E is empty
- 45complementcomplement of G is Gbar. Gbar is the graph with the same vertex set but an edge set consisting of all edges not present in G
- 46regular graph / regular graph of degree r / r-regularevery vertex has same degree r
- 47subgraphH is a subgraph of G if V(H) is a subset of V(G) and E(H) is a subset of E(G)
- 48induced grapha subgraph of G induced by S is a graph with all vertices in S and all edges {uv | u,v in S and uv in E(G)}
- 49bipartite graphvertex set can partitioned into two sets X,Y such that every edge G has one vertex in X and another in Y
- 50complete bipartite graphif the edge set E is such that E={xy | x in X, y in Y}
K_{|X|,|Y|}
- 51thm: bipartite and odd cyclesa graph with at least 2 vertices is bipartite IF AND ONLY IF it contains no odd cycles
- 52Eulerian trailtrail in a graph G that includes every edge of G
- 53Eulerian circuitcircuit that includes every edge of the graph
- 54Eulerian grapha graph that contains an Eulerian circuit
- 55thm: Eulerian characterizationall equivalent:
1) G is Eulerian
2) every vertex of G has even degree
3) the edges of G can be partitioned into (edge-disjoint) cycles - 56cor: eulerian trail and vertices of odd degreeconnected graph G contains an Eulerian trail IF AND ONLY IF there are at most two vertices of odd degree
- 57Eulerian theorem (not directed)Eulerian path on a finite connected graph exists IF AND ONLY IF there are exactly 0 or 2 vertices of odd degree
multiple edges, loops are okay - 58Eulerian notion of degree for directed graph# incoming edges - # outgoing edges
- 59Euler's thm (directed)Eulerian path exists IF AND ONLY IF either all degrees are 0 or all but two degrees are 0. In latter case, degrees are 1, -1
- 60number of vertices of odd degree in a connected graph is 0for a circuit/cycle, start = finish
- 61number of vertices of odd degree in a connected graph is 2for a circuit/cycle, start isn't the same as the finish
- 62isomorphismtwo graphs G,H are isomorphic if there is a bijection f from the vertex set of G onto that of H s.t. the number of edges between any pair of vertices X and Y of G is equal to the number of edges between vertices f(X) and f(Y) of H. the bijection is called an isomorphism
- 63automorphisman automorphism of a graph F is an isomorphism between G and G itself
- 64Hamiltonian cyclecycle which includes visits all vertices of a graph exactly once
- 65Hamiltonian patha path that includes all vertices of a graph
- 66degrees and Hamiltonian cyclesn>=3. Let G be a simple graph with n vertices, all of which have degree at least n/2. Then G has a Hamiltonian cycle
Informationen
- Beschreibung
- Mathematics Karteikarten am graph theory, erstellt von Daphne David am 02/04/2019.
- Erstellt von
- Daphne David
- Aufrufe
- 0
- Bewertung