APRENDE GRAFOS DESDE CERO: Grafos básicos, lista y matriz de adyacencia, definiciones y propiedades.
Graphs: An Introduction to Key Concepts
What is a Graph?
- A graph is a data structure consisting of vertices (nodes) and edges (connections) that represent relationships or connections between entities.
- The degree of a vertex refers to the number of edges connected to it, indicating its connectivity within the graph.
Types of Graphs
Path and Cycle Graphs
- Path Graph: Vertices are connected sequentially without connecting the ends, denoted by the letter P.
- Cycle Graph: Each vertex connects to two others forming a closed loop, represented by the letter C.
Wheel and Complete Graphs
- Wheel Graph: All but one vertex form a cycle, with connections to a central vertex; denoted by W.
- Complete Graph: Every vertex is interconnected; represented by K (from "komplett" in German).
Bipartite and Complete Bipartite Graphs
- Bipartite Graph: Composed of two groups of vertices where no intra-group connections exist, only inter-group ones. If fully connected, it's called Complete Bipartite, denoted as K with subscripts for group sizes.
Representing Graphs
Different Representation Methods
- Three primary methods for defining graphs:
- Formal Definition: Naming vertices and edges using braces.
- Adjacency List: A list detailing each vertex's adjacent vertices.
- Adjacency Matrix: A square matrix where rows/columns represent vertices; filled with 1 if connected or 0 if not. Diagonal elements are zero in simple graphs.
Directed and Weighted Graphs
Directed Graph Representation
- In directed graphs, edges become arrows indicating direction (arcs), changing representation from unordered pairs 1,2 to ordered pairs (1,2). Adjacency matrices for directed graphs are non-symmetric.
Weighted Edges
- Weighted graphs associate numerical values (weights) with edges; these weights replace binary indicators in adjacency matrices when representing connections. Denoted by W for weight.
Multigraphs and Isomorphism
Understanding Multigraph Characteristics
- Multigraphs allow multiple edges between vertices or loops on vertices; their adjacency matrix reflects connection counts rather than binary presence/absence indicators. Diagonal entries may be non-zero due to loops present in the graph structure.
Isomorphic and Planar Graph Properties
- Two graphs are isomorphic if they can be transformed into one another through rearrangement while maintaining structural integrity (shape). A planar graph has no intersecting edges—e.g., K4 is planar while K5 cannot be arranged without intersections due to its complexity.
Additional Concepts in Graph Theory
Complementary and Connectedness Properties
- A complementary graph results from removing certain edges while adding new ones where none existed; if this new graph is isomorphic to the original, it’s termed self-complementary.
- Connectivity indicates whether all vertices can be reached via paths within the graph.
Cyclic Nature of Graph Paths