GT Test Two Flashcards
Minimum postman’s walk
A closed walk of G that contains every edge of G and is of minimum total length
Minimum salesman walk
A closed walk of G that contains every vertex of G and is of minimum total length
Ore’s theorem
If G is a graph with p<= 3 vertices & for any pair of non-adjacent vertices x & y, deg(x)+deg(y)=> , then G has a Hamilton cycle
Polyhedral Graph
Is a graph that is obtained by considering the vertices and edges of a polyhedron P as vertices and edges of a graph
Dual Graph G*
The graph obtained by considering the faces of P as vertices and for each each that is shared by two faces, there will be an edge in G*
Open Euler-trail of G
An open Euler trail of G is any walk in G which includes each edge of G exactly once and with starting vertex ≠ terminal vertex
Hamilton-connected
A graph G is hamiton-connected if there is a hamilton path between any two distinct vertices of G
Dual of the planar graph G
The dual G* of G is the graph where V(G)= set of regions into which E partions the plane and for each edge between the regions R1&R2 in E, we get an Edge between R1&R2 in E(G)
Maximal path of G
Any path P in G such that there is no other path P’ of G which properly contains P.
Convex polyhedron
A polyhedron Q is convex if any line that joins two points of Q always lies inside Q
Maximal planar G
If G is planar and for any pair of non adjacent vertices x&y in G, GU{xy} (bar) is non-planar
Simple polyhedron
Any solid figure bounded by plane polygonal faces that can be continuously distorted into a solid sphere.
Homeomorphic
Two graphs G and H are homeomorphic if we can transform G into H by creating vertices of degree 2 on certain edges of G or by merging out certain vertices of degree 2 in G.
Kurotowski’s planarity theorem
G is planar if and only if G has no sub graph which is homeomorphic to k5 or k3,3
