Flashcards

graph theory

Daphne David Mathematics English 66 cards

Cards in this deck (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