Graph Terminology
- vertex/node - is usually represented by a circle with a label
Click here to expand...
- labeled vertex - is a vertex that is associated with extra information that enables it to be distinguished from other labeled vertices
- unlabeled vertex - is a vertex
- vertex degree 𝛿(v) - is the number of edges incident to said vertex
- isolated vertex - is a vertex of 0 degree
- leaf vertex or pendant vertex - is a vertex of 1 degree
- source vertex - is a vertex with in-degree zero
- sink vertex - is a vertex with out-degree zero
- simplicial vertex - is a vertex whose neighbors form a clique: every two vertex in clique are adjacent
- universal vertex - is a vertex that is adjacent to every other vertex in the graph
- cut vertex - is a vertex the removal of which would disconnect the remaining graph
- edge - is represented by a line or arrow extending from one vertex/node to another
Click here to expand...
- undirected edge - unordered pair of vertices
- directed edge - ordered pair of vertices
- bi-directed edge - an edge that is given an independent orientation (or direction, or arrow) at each end. there are three kinds of bi-directed edges:
- extraverted - those where the arrows point outward, towards the vertices, at both ends
- introverted - those where both arrows point inward, away from the vertices
- directed (same as ordinary directed edges) - those in which one arrow points away from its vertex and towards the opposite end, while the other arrow points in the same direction as the first, away from the opposite end and towards its own vertex
- half-edges - an edge with only one arrow
- loose edge - an edge with no arrows
- ordinary edges - an edge that is neither half edge nor loose edge
- loop or edge loop or self loops - an edge where both ends connects to the same vertex
- parallel edge - an edge where there is another edge connecting to the same vertices u and v
Bi-Directed Edges
List indent undo
- graph - consists of 2 sets: a set of vertices/nodes and a set of edges
Click here to expand...
- undirected graph - a graph whose set of edges are all undirected edges
- tree (singly connected acyclic undirected graph) - an undirected graph in which any two vertices are connected by exactly one path
- balanced tree - a tree where every leaf node is “not more than a certain distance” away from the root than any other leaf node
- full binary tree - is a tree in which every node other than the leaves has 2 children
- complete binary tree - a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible
- undirected tree - same as a tree (graph with no cycles)
- binary tree - a tree in which each node has at most two children
- binary search tree - a type of ordered tree
- AVL tree - a self-balancing binary search tree
- binary search tree - a type of ordered tree
- heap - a specialized tree which is essentially an almost complete tree that satisfies the heap property (e.g. min or max)
- tree (singly connected acyclic undirected graph) - an undirected graph in which any two vertices are connected by exactly one path
- directed graph (digraph) - a graph whose set of edges are all directed edges https://www.youtube.com/watch?v=1SxH02CjCDQ
- directed acyclic graph (DAG) - a directed graph without directed cycles
- polytree (singly connected acyclic directed graph) - a directed acyclic graph whose underlying undirected graph is a tree. has one or more root nodes (nodes without parents), and for each node, there is exactly one path from it to the root
- directed tree - a polytree with only 1 root node (node with no parents)
- directed acyclic graph (DAG) - a directed graph without directed cycles
- stump - a tree where its root node has only leaves
- simple graph - a graph without loops and without parallel edges
- complex graph - a graph with loops and/or parallel edges
- bipartite graph - a graph with no odd cycles
- complete bipartite graph - a graph where vertices from one set
- homomorphic graph - 2 graphs are equal if their vertex-set and edge-set are equal
- isomorphic graph - 2 graphs are isomorphic if you can make them homomorphic by relabelling their vertices
- forest - is a graph containing only trees
- poly forest - is a directed acyclic graph whose underlying undirected graph is a forest
- subgraph - is formed from a subset of the vertices of the graph and a SUBSET of edges connecting pairs of vertices in that subset
- induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ALL of the edges connecting pairs of vertices in that subset
- spanning subgraph - is a subgraph without cycles that contains all the vertices of the original graph. resulting in either:
- spanning tree - an acyclic component
- spanning forest - a set of spanning trees
- clique - a subgraph where its set of vertices form a complete graph
- connected component - an undirected graph where there is a path between every 2 nodes
- strongly connected component - a directed graph where there is a path between every 2 nodes
- connected graph - an undirected graph where every pair of vertices 𝑥,𝑦 ∊ 𝑉(𝐺), there exists a path with endpoints 𝑥 and 𝑦
- 2-connected graph - a connected graph where for every vertex 𝑥∊𝑉(𝐺), 𝐺-𝑥 is a connected graph
- k-connected graph - a connected graph where for every vertex-set of size 𝑘, 𝑣𝑒𝑟𝑡𝑒𝑥-𝑠𝑒𝑡 ∊ 𝑉(𝐺), 𝐺 - 𝑣𝑒𝑟𝑡𝑒𝑥-𝑠𝑒𝑡 is a connected graph
- complete graph - an undirected graph where every vertex is adjacent to every other vertex (this graph has 𝑛(𝑛-1)/2 or [𝑛 choose 2] edges)
- undirected graph - a graph whose set of edges are all undirected edges
Other Terminology
- walk - a walk between nodes 𝑢 and 𝑣 is a node sequence
- starting with 𝑢 and ending with 𝑣
- where each node in the sequence is adjacent to the next node in the sequence
- edge and node repetitions allowed
- trail - a walk between 2 nodes WITHOUT edge repetitions
- path - a walk between 2 nodes WITHOUT node repetitions
- geodesic - the shortest path between 2 nodes
- circuit - a trail that starts and ends on the same vertex
- cycle - a path that starts and ends on the same vertex
- distance - the distance between nodes 𝑢 and 𝑣 is the length of the shortest path between nodes 𝑢 and 𝑣
- eccentricity - the eccentricity of a vertex 𝑣 is the maximum of all distances between vertex 𝑣 and every other vertex
- diameter - the diameter of a graph is the maximum of all eccentricities in the graph
- radius - the radius of a graph is the minimum of all eccentricities in the graph
- peripheral - is a vertex whose eccentricity is equal to the diameter of the graph
- periphery - is the set of peripherals in a graph
- central - is a vertex whose eccentricity is equal to the radius of the graph
- centre - is the set of centrals in a graph