Matdis 32: Graf (Bagian 1-02: Terminologi di dalam Graf)

Summary

In this video, Fariska explains key terminologies in graph theory, including adjacency, incidence, isolated vertices, null graphs, and degree. The concepts are illustrated with examples from various graphs, demonstrating how vertices are connected, how edges relate to vertices, and how degree is calculated. Fariska also introduces the Handshaking Lemma, which states that the sum of degrees in a graph is twice the number of edges. The video delves into further details, such as odd-degree vertices and the relationship between graph structure and degree sums, helping viewers understand the foundational concepts of graph theory.

Takeaways

• 😀 The script introduces important graph terminologies, starting with adjacency and how two vertices are adjacent if they are directly connected.
• 😀 A vertex is said to be incident with an edge if the edge connects it, and the script explains this concept with examples.
• 😀 An isolated vertex is a vertex with no edges connecting to it, exemplified by a vertex in graph G3.
• 😀 A null graph, also known as an empty graph, is a graph where the set of edges is empty, and it is demonstrated with an example.
• 😀 The degree of a vertex refers to the number of edges incident to it, with examples showing how the degree is calculated in various graphs.
• 😀 The script explains the concept of loop edges, which count as two towards the degree of a vertex.
• 😀 In directed graphs, the in-degree and out-degree of a vertex are defined as the number of edges coming into and going out of the vertex, respectively.
• 😀 The Handshaking Lemma states that the sum of the degrees of all vertices in a graph is always even, which is equal to twice the number of edges in the graph.
• 😀 The script provides examples of graphs and calculates the sum of degrees to verify the Handshaking Lemma, with consistent results.
• 😀 A key theorem derived from the Handshaking Lemma states that a graph cannot have an odd number of vertices with odd degrees, always resulting in an even count of such vertices.

Q & A

What does it mean for two vertices to be adjacent in a graph?

Two vertices are considered adjacent if they are directly connected by an edge. For example, in graph G1, vertex 1 is adjacent to vertex 2 and vertex 3, but not adjacent to vertex 5.

What is the definition of incidence in graph theory?

Incidence refers to the relationship between an edge and the vertices it connects. For example, in graph G1, edge 2-3 is incident to both vertices 2 and 3.

What is an isolated vertex?

An isolated vertex is a vertex that has no edges incident to it. In graph G3, vertex 5 is an isolated vertex because it is not connected to any other vertex.

What is a null graph?

A null graph, or empty graph, is a graph that contains no edges. For example, in the case of graph G5, the set of edges is empty.

What does the degree of a vertex represent in a graph?

The degree of a vertex represents the number of edges incident to it. For instance, in graph G1, the degree of vertex 1 is 2, as it is connected to vertices 2 and 3.

How are the in-degree and out-degree of a vertex in a directed graph different?

In a directed graph, the in-degree of a vertex is the number of edges directed towards it, while the out-degree is the number of edges directed away from it. For example, in graph G4, vertex 1 has an in-degree of 2 and an out-degree of 1.

What is the Handshaking Lemma in graph theory?

The Handshaking Lemma states that the sum of the degrees of all vertices in a graph is always even, as it is equal to twice the number of edges in the graph.

What does the Handshaking Lemma imply about the number of vertices with odd degrees in a graph?

The Handshaking Lemma implies that the number of vertices with odd degrees in any graph is always even. This is because the total degree of the graph is even.

Can a graph exist with an odd number of vertices having an odd degree?

No, a graph cannot have an odd number of vertices with an odd degree. According to the Handshaking Lemma, the number of vertices with odd degrees must always be even.

What is the difference between an undirected graph and a directed graph in terms of vertex degree?

In an undirected graph, the degree of a vertex is simply the number of edges incident to it. In a directed graph, the degree is split into in-degree and out-degree, representing the number of incoming and outgoing edges, respectively.