1819507
Description
Flashcards by florencetrodd, updated more than 1 year ago
|
Created by florencetrodd
over 10 years ago
|
|
| Question | Answer |
| Edge | An edge is an unordered pair of vertices i.e. {v, w} € E |
| Adjacent (for vertices and edges) | Two vertices v, w € V are adjacent if there is an edge between v and w. Two edges e, f € E are adjacent if they have a common endpoint |
| Neighbours Neighbourhood | Neighbours of x are the vertices adjacent to x. The set of adjacent vertices of x is called the neighbourhood of x, N(x). |
| A vertex is incident to an edge if | the vertex is an endpoint of the edge |
| The complement of G | The complete graph K (v(G)) minus G. |
| Coprime Graph | Vertices are joined by an edge if the gcd of the edges is 1 |
| isomorphism of G onto H | one-to-one map @ from V(G) onto V(H) where a and b are adjacent vertices in G if a@ and b@ are adjacent vertices in H |
| If G=< H, the complement of G in H is | H-G |
| Degree d(x) | the number of edges that have x as an endpoint |
| delta (x) DELTA (x) | delta (x) is the minimum degree in the graph DELTA (X) is the maximum degree in the graph |
| Let G be a finite simple graph | A graph with: - at most one edge between any pair of distinct vertices (no loops). -the edge is NOT directed. - finite vertex set -finite edge set |
| The Hand-Shaking Lemma | the sum of d(x) = 2|E(G)| |
| Walk | LGBAFSG a walk is a finite sequence of vertices and edges: x0, a1, x1, a2, ..., an, xn |
| simple walk | only distinct edges |
| length of a walk | number of edges |
| Path | a walk where all the vertices are distinct |
| closed walk | x0 = xn i.e. the first vertex is the same as the last vertex |
| A Cycle of length n | A closed walk of length n, where the vertices x0, ..., xn-1 are distinct |
| Theorem 2.1 If there is a walk between vertices y and z, y/=z, then | there is a path in G with first vertex y and last vertex z |
| two vertices are connected when... | there is a walk joining them |
| two vertices are connected iff... | they lie in the same component of G |
| G is a connected graph iff | all pairs of its vertices are connected i.e. if there is a walk between any two distinct vertices |
| If vertices y,z € V are connected, their distance D(x,y) is...? | the length of the shortest path joining them |
| What are the three properties of D(x,y) ? | 1) D(x,y) >= 0 with D(x,y)=0 iff x=y 2) D(x,y) = D(y,x) ... symmetry 3) D(x,z) =< D(x,y) + D(y,z) ... triangle inequality |
| eccentricity | the largest value of D(x,y) where y ranges through all the vertices |
| diameter | The maximum value of e(x) for all vertices of G |
| radius | the smallest value of e(x) |
| Conjecture involving radius and diameter | R(G)=< D(G) =< 2R(G) |
| Centre | The centre of G, C(G), is the set of all vertices x that have eccentricity e(x) = R |
| The centre is never ... ? | empty. All vertices have e(x). |
| H is a subgraph of G if | V(H) is a subgroup of V(G) E(H) is a subgroup of E(G) |
| H is a proper subgraph if | H /= G i.e. H<G |
| induced subgraph | H is the induced subgraph of G if: H is a subgroup of vertices of G together with the edges that join the vertices of H together. |
| If H is the induced subgraph of G on V(G), then | H=G |
| girth | the length of the shortest cycle in G |
| circumference | the length of the longest cycle in G |
| True or false? circumference (G) =< |V(G)| | True |
| In a cycle Cn, what does |V(Cn)| equal? | |E(Cn)| |
| Eulerian Graph | a graph G that admits a closed eulerian walk |
| Eulerian Walk | simple closed walk containing every edge |
| semi-eulerian graph | A graph that has a non-closed eulerian walk |
| Theorem 2.6 LGBAFSCG. G is eulerian iff every ?? has ?? degree G is semieulerian iff there exists exactly ?? ?? of ?? degree | G is eulerian iff every vertex has even degree G is semieulerian iff there exists exactly two vertices of odd degree |
| Hamiltonian Graph | LGBAFSCG G is hamiltonian if G admits a cycle containing all the vertices |
| Semihamiltonian Graph | G is semihamiltonian if G admits a path containing all the vertices |
| Two examples of hamiltonian graphs | (n =<3) Cn Kn |
| Ore's Theorem | LGBAFSCG with |V(G)| >= 3 Suppose that d(x) + d(y) >= |V(G)| for all pairs x,y of non-adjacent vertices Then G is Hamiltonian |
| Dirac's Corollary | LGBAFSCG with |V(G)| >= 3 If d(x) >= V/2 for all x, then G is Hamiltonian |
| G is bipartitie iff G contains no ?? | LGBAFSG. G is bipartite iff G contains no cycles of odd length |
| G is bipartite if | V(G) = A U B A n B cannot be empty A, B cannot be empty E(G) join all vertices in A to all vertices in B |
| Examples of bipartite graphs | complete bipartite graphs K m,n Cycles of even length |
| When is the bipartite graph Hamiltonian? | m=n >= 2 |
| When is the bipartite graph never hamiltonian? | if m doesn't equal n |
| Eulerian walk | covers all edges exactly once repeated vertices are allowed |
| hamiltonian cycle | covers all vertices exactly once, repeated edges are allowed |
| The complement of G on V vertices | The complete graph on V vertices minus G |
| cutpoint | x € V(G) is a cutpoint if G-x isn't connected |
| bridge cutedge | an edge xy € E(G) such that G-xy is not connected |
| Lemma 3.1 an edge xy € E(G) is a bridge iff | xy is not contained in any cycle in G |
| Lemma 3.2 how many components does G-xy have if xy € E(G) is a bridge? | two |
| If the degree of all x € V(G) is even, is there a bridge in G? | No |
| If there is an xy bridge in G, what effect does this have on the degree in G? | d(x) is even for all the vertices |
| connectivity | The connectivity of G, K(G), is the minimum value of n such that the removal of some set of n vertices disconnects G or results in a single vertex. |
| What does K(G)=0 mean? | G is disconnected from the start |
| What does K(G) = 1 mean? | G has a cutpoint |
| K(G) >= K | G is k connected |
| edge connectivity k'(G) | K'(G) is the minimum value of m such that the removal of some set of m edges disconnects G |
| K(G) =< K'(G) =< delta(G) | K(G) =< K'(G) =< delta(G) |
| general walk | no loops |
| G is nonseperable if | G is nontrivial, connected and has no cutpoints |
| A block in G | maximal non-seperable subgraph |
| A proper n-colouring of V(G) | %:V(G) -> {1, .., n} so that if x,y€V(G) are adjacent, %(x) /= %(y) |
| chromatic number X(G) | smallest integer n such that G has an n-colouring |
| Colourings (general) | partitions of the vertex or edge set of a graph into subsets so that no two elements of the same subset are adjacent |
| Are the following eulerian/ semieulerian? N3 N4 N5 N6 N7 | N3: eulerian N4: semieulerian N5: semieulerian N6: neither N7: semieulerian |
0 comments
Want to create your own Flashcards for free with GoConqr? Learn more.