Graph Theory Flashcards
(42 cards)
What does κ(G) represent?
minimal vertex cut
What does λ(G) represent?
minimal edge cut
What does ω(G) represent?
number of components
What does δ(v) represent?
degree of v
What does |x| represent?
number of “x” – NOT absolute value
How many edges are in a complete graph?
n(n-1) / 2
What is the sum of the degree of all vertices?
∑v∈v(g) δ(v) = ?
Twice the number of edges. 2*|E(G)|
When is a degree sequence graphic?
If there is a corresponding simple graph.
If you sum up the contents of a row in an adjacency or incidence matrix, what is the resulting number?
The degree of the vertex. δ(v)
If each vertex in a graph G1 is associated with a vertex in a graph G2 such that the edges correspond, we can say G1 and G2 are:
isomorphic.
Two vertices are connected if:
there is a path between them.
A graph is connected if:
all pairs of vertices are connected.
i.e. from any vertex, there is a path to any other vertex.
What is a component of G?
A connected subgraph that isn’t strictly contained another connected subgraph of G.
What is the difference between a walk and a path?
A walk is just a sequence of vertices and edges.
In a path, all vertices the vertices are unique.
i.e. you never cross the same vertex twice.
What are vertex/edge cuts?
A subset of the vertices/edges such that if you take them away from the graph, the graph will become disconnected.
What can we say about the minimal: vertex cut, edge cut, and degree of vertices in a graph?
The minimal vertex cut is less than or equal to the minimal edge cut which is less than or equal to the minimal degree of the vertices in a graph.
κ(G) ≤ λ(G) ≤ min v∈V(G) {δ(v)}
What is the minimal vertex/edge cut?
The minimum number of vertices/edges you have to remove to disconnect the graph.
What does it mean if a graph is k-connected?
that the minimal vertex cut is greater than or equal to k.
κ(G) ≥ k
i.e. it has more than k vertices and remains connected whenever fewer than k vertices are removed. You have to remove k+ vertices to disconnect the graph.
If you have two non-adjacent vertices (u,v), the number of vertex independent paths between (u,v) is equal to:
The minimum number of vertices you need to remove to disconnect u and v. (by Mengers Theorem)
By Mengers Theorem, the minimum number of vertices you need to remove to disconnect two non-adjacent vertices u and v is equal to:
The number of vertex independent paths between u and v.
Which property is “stronger” vertex independence, or edge independence?
Vertex independence. Since vertex independence implies edge independence, but not vice versa.
These properties represent what type of graph?
- V(G)=V1∪V2
- V1 ∩ V2 = {}
- E(G)⊆{⟨v1,v2⟩ | v1 ∈V1 and v2 ∈V2}
Additionally, translate each of the above lines into english.
Bipartite graph.
- The vertex set of G is equal to the union of vertex set V1 and vertex set V2.
- V1 and V2 have no elements in common. Meaning, V1 and V2 share no vertices.
- The edge set E(G) contains edges whose endpoints are in different sets.
What is a ranked embedding?
A type of graph embedding that can be performed on bipartite graphs such that each “row” of the embedding contains vertices from a different set.
How does a spring embedding work? (simply)
A spring embedding is constructed by assigning attractive forces to adjacent vertices, and repelling forces to non-adjacent vertices. Calculations are then performed until an equilibrium is achieved, and then you’ll have the result of the embedding.
