(prerequisite-CNN) Graph, Vertex(Node), Edge

CNN typically uses images as data. How? The image is expressed by Vertex(Node) and Edge.

 

• graph

 

Composed of Vertex(Node), Edge. In other words, set of Vertex(Node)and Edge.

 

• Vertex(Node)

 

It is the fundamental unit of which graphs are formed.

Featureless and indivisible objects.

 

• Edge(Arc)

It represented by a line or arrow extending from one vertex to another.

Relationship between vertexes.

 

 

• Sparse Graph VS Dense Graph

Sparse Graph VS Dense Graph

 

• Sparse Graph

It has fewer edges than the number of nodes.

 

• Dense Graph

It has more edges than the number of nodes.

 

• Loop Vertex VS Isolated Vertex

• Loop Vertex

Loop Vertex

 

When one edge is belong to the same node.

 

• Isolated Vertex

Graph with isolated vertex a.

 

 It is not an endpoint of any edge.

 

• Isomorphic

Graph 1

Graph 2

 

The graph expressed differently due to differences in ordering of nodes but have the same structure.

Comparing the two graphs, it looks different. However, the two graphs have exactly the same structure.

 

https://process-mining.tistory.com/167

 

• Complete Graph VS Multi Graph

 

• Complete Graph

All nodes are connected by edges, so the graph with the maximum number of edges.

 

• Multi Graph

If there is one or more edges between nodes, the corresponding edges are called transitive, and this graph is called multigraph.

 

• Clique

 

A "subset of the nodes" in an undirected graph.

In the case of above, there are Cliques as below.

• 𝑎,𝑏
• 𝑎,𝑐,𝑑
• 𝑏,𝑔
• 𝑐,𝑑,𝑒,𝑓 (maximum Clique)
• 𝑐,𝑓,ℎ
• 𝑓,𝑔

 

https://www.tutorialspoint.com/cliques-in-graph

 

• Directed Graph(Digraph)

 

• Directed Graph(Digraph)

A directed graph is a graph that is unidirectional in this the edges have a specific direction and the edges have directions specified with them also a directed graph can contain cycles.

 

• Undirected Graphs

 An undirected graph is a graph where the edges do not have a specific direction and it is bidirectional in nature it does not have a parent-child relation concept as there is no particular direction.

 

• Predecessor(Source)
• Successor(Sink)
• Outgoing Edge
• Incoming Edge
• Incoming Degree
• Outgoing Degree

 

If there is edge 𝑒1 from 𝑉2 to 𝑉1, 𝑉2 is called the preservice/source and 𝑉1 is called the successor/sink. At this time, 𝑒1 is called the outgoing edge of 𝑉2 and the incoming edge of 𝑉1.

 

In the direction graph, the incoming degree of 𝑉1 is 𝑒1, and the outgoing degrees are 𝑒2, 𝑒3.

 

• Path

A sequence of adjacent nodes (one or more).

 

• Simple

Paths that do not overlap with edges.

 

• Elementary

Paths that do not overlap with nodes.

 

Sequence 1. [𝑣1,𝑣2,𝑣3,𝑣4,𝑣5,𝑣3,𝑣4,𝑣5]
Sequence 2. [𝑣1,𝑣2,𝑣3,𝑣4,𝑣5,𝑣8,𝑣6,𝑣4,𝑣7]

 

-Sequence 1 : The edges and nodes overlap, it is neither simple nor elemental.

-Sequence 2 :  It's simple because the edges don't overlap. But it's not elementary because the nodes overlap.

 

https://juyoungit.tistory.com/568#Path

https://ratsgo.github.io/data%20structure&algorithm/2017/11/18/graph/#