Graph Theory Concepts - 7/4

Definition of a semi-Hamiltonian graph

• A semi-Hamiltonian graph contains a path that includes every vertex once only but is not a cycle.

• A semi-Hamiltonian graph is a graph that contains a cycle visiting every vertex exactly once.

• A semi-Hamiltonian graph is a complete graph with all vertices connected in a cycle.

• A semi-Hamiltonian graph is a graph that has no cycles at all.

Network

• A system used for data storage and retrieval.

• A system often used in everyday life, such as television or rail networks, and can represent trails, social networks, transport networks, food webs, and sporting competitions.

• A type of software application for managing tasks.

• A collection of unrelated devices and systems.

Weighted graphs

• A weighted graph is a graph in which each edge is labelled with a number used to represent some quantity associated with the edge.

• A graph that contains only vertices and no edges.

• A graph that is used to represent hierarchical data structures.

• A graph that has all edges of equal length.

Definition of a planar graph

• A graph that can be drawn on a plane without any edges crossing.

• A graph that has at least one cycle.

• A graph that can be represented in three-dimensional space.

• A graph that contains no vertices.

Path

• A sequence of edges that connect a sequence of vertices.

• A collection of nodes without any connections.

• A single edge connecting two vertices.

• A random arrangement of vertices.

Bridge in a graph

• An edge in a connected graph that, if removed, leaves the graph disconnected.

• A vertex in a graph that connects two separate components.

• A cycle in a graph that connects all vertices.

• An edge that can be removed without affecting the connectivity of the graph.

Difference between Hamiltonian and semi-Hamiltonian graphs

• A Hamiltonian graph forms a cycle, while a semi-Hamiltonian graph does not.

• Both Hamiltonian and semi-Hamiltonian graphs form cycles.

• A Hamiltonian graph has no cycles, while a semi-Hamiltonian graph does.

• Semi-Hamiltonian graphs are always complete graphs.

Definition of a loop in a graph

• A loop is an edge in a graph that joins a vertex to itself.

• A loop is a sequence of edges that connects two different vertices.

• A loop is a type of graph that contains no cycles.

• A loop is a vertex that has no edges connected to it.

Definition of a complete graph

• A complete graph is a simple graph in which every pair of distinct vertices is connected by a unique edge.

• A complete graph is a graph that contains no edges.

• A complete graph is a graph where all vertices are isolated.

• A complete graph is a graph that has at least one loop.

Cycle

• A cycle is a closed path which begins and ends at the same vertex and has no repeated edges or vertices except the first.

• A cycle is a sequence of edges that connects two vertices without forming a loop.

• A cycle is a path that can have repeated vertices but not repeated edges.

• A cycle is a closed path that can include multiple vertices but must have at least one repeated edge.