Degree of a Vertex
Undirected Graph: The number of edges incident to the vertex.
Digraph (Directed Graph): Split into in-degree (incoming edges) and out-degree (outgoing edges).
Complement of a Graph
Obtained by connecting vertices that are not connected in the original graph and not connecting vertices that are connected in the original graph, within the same vertex set.
Graphical Degree Sequence
A list of non-negative integers in non-increasing order, each representing the degree of a vertex in the graph. It must satisfy the Handshaking Lemma and the Erdős–Gallai theorem for it to be graphical.
Graph Representation Methods
Adjacency Matrix: A square matrix used to represent a finite graph. The elements indicate whether pairs of vertices are adjacent.
Adjacency List: A collection of lists or arrays, one for each vertex, listing the adjacent vertices.
Edge List: A list of edges, where each edge is represented as a pair (or triplet for weighted graphs) of vertices.
Subgraph and Proper Subgraph
Subgraph: Formed from a graph by selecting some of its vertices and edges.
Proper Subgraph: A subgraph that contains a subset of the vertices and edges of the graph and at least one vertex or edge less than the original graph.
Weighted Graph
A graph where each edge has a numerical value, or weight, associated with it, representing a quantitative relationship between the vertices.
Bipartite Graph
Defined as a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. No edge connects vertices within the same set.
Regular Graph
A graph where each vertex has the same number of neighbors; i.e., every vertex has the same degree.
Line Graph
Obtained from a graph by representing each edge of the original graph as a vertex in the line graph, and connecting two vertices in the line graph if and only if their corresponding edges in the original graph are incident to the same vertex.
Union of a Graph and Its Complement
Results in a complete graph, as every possible edge between vertices in the graph is included either in the graph or its complement.
Graph Union vs. Graph Join
Union: Combines two graphs by taking the union of their vertex sets and edge sets.
Join: Similar to union, but adds an edge between every pair of vertices from different graphs.
Trail vs. Path
Trail: A walk in which all edges are distinct.
Path: A trail in which all vertices (and hence edges) are distinct.
Eularian Tour and Cycle
Eulerian Tour: A trail in a graph that visits every edge exactly once.
Eulerian Cycle: An Eulerian tour that starts and ends on the same vertex.
Eulerian Tour Existence: Not every graph has an Eulerian tour. A graph has an Eulerian tour if and only if it is connected and every vertex has an even degree.
Hamiltonian Tour and Cycle
Hamiltonian Tour: A path in a graph that visits every vertex exactly once and can end at a different vertex.
Hamiltonian Cycle: A Hamiltonian tour that starts and ends on the same vertex.
Distance between Two Vertices
Unweighted Graph: The minimum number of edges to be traversed to get from one vertex to another.
Weighted Graph: The minimum sum of edge weights on a path from one vertex to another.
Eccentricity and Radius
Eccentricity: The maximum distance from a vertex to all other vertices in the graph.
Radius: The minimum eccentricity among all vertices in the graph.
Graph Isomorphism
Two graphs G and H are isomorphic if there is a bijection between the vertex sets of G and H that preserves adjacency. This means a way exists to "relabel" the vertices of G to get H while keeping the structure of connections between vertices the same.
ความคิดเห็น