Some Of Graph Theory Related Terminology.
* Loop: An edge connecting a vertex to itself.
* Directed Edge: Each edge has a direction.
* Simple Graph: Graph with no loops or multi-edges.
* Walk: A sequence v0e1v1 . . . envn.
* Trail: A walk with distinct edges.
* Path: A trail with distinct vertices.
* Connected Graph: A graph where there exists a path between any two vertices.
* Component: A maximal connected subgraph.
* Tree: A connected acyclic graph.
* Free tree: A tree with no root.
* DAG: Directed acyclic graph.
* Eulerian Graph: Graph with a trail visiting each edge exactly once.
* Hamiltonian Graph: Graph with a cycle visiting each vertex exactly once.
* Cut: A set of edges whose removal increases the number of components.
* Cut-set: A minimal cut.
* Cut-edge: A size 1 cut.
* k-Connected: A graph connected with the removal of any k − 1 vertices.
* k-Regular: A graph where all vertices have degree k.
* k-Factor: A k-regular spanning subgraph.
* Matching: A set of edges, no two of which are adjacent.
* Clique: A set of vertices, all of which are adjacent.
* Independent set: A set of vertices, none of which are adjacent.
* Vertex cover: A set of vertices which cover all edges.
* Planar graph: A graph which can be embeded in the plane.
* Plane graph: An embedding of a planar graph.
No comments:
Post a Comment