A forest is a graph that contains no cycles, and a connected forest is a tree. For example, Fig. 1.1 shows a forest with four components, each of which is a tree

". Note that trees and forests are simple graphs.

                                                               Fig. 1.1

Another definition

A forest is an acyclic graph. The connected components of a forest are therefore trees, which explains the use (very natural!) of the terminology.

Forests generalize trees.

Proposition 1.1. In a forest G, we have m ≤ n − 1, with equality if and only if G is a tree.

Proof. Given C₁, C₂, ..., C_p the connected components of G, apply proposition( If G is a tree then m = n − 1.) to each of these components, denoting respectively n_i and

m_i the number of vertices and the number of edges of C_i. By adding all these equalities, for i =1, 2,...,p, we then have:

Thus:

                                m = n − p

and since p ≥ 1(p is the number of connected components of G):

                               m ≤ n − 1

Equality occurs if and only if p = 1, that is if and only if G is connected. Since G is by hypothesis acyclic, this means if and only if G is a tree.

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(47)

Introduction to  Graph Theory  ,Fourth edition,  Robin J. Wilson, 1998

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم الشؤون الفكرية يطلق فعاليات الأسبوع الثالث من برنامج البذرة الصالحة

تكريم الفائزين في المسابقة الثقافية الخاصّة بذكرى ولادة الإمامين الباقر والهادي (عليهما السلام)

بذكرى ولادتهما.. العتبة العباسية المقدسة تستذكر السيرة العطرة للإمامين الباقر والهادي (عليهما السلام)

العتبة العباسية المقدسة تنظم احتفالها المركزي بذكرى ولادة الإمامين الباقر والهادي (عليهما السلام)

المزيد

الآخبار الصحية

ثورة طبية.. الذكاء الاصطناعي يكشف سرطان الكلى في وقت قياسي

لتعزيز الطاقة والتغلب على التعب.. عليك بـ7 طرق بسيطة

لتحسين الهضم والتحكم في الشهية.. ما أفضل وقت لتناول التمر؟

خبراء يكشفون تأثير الاستحمام في الظلام على جودة النوم !

المزيد

الآخبار التكنلوجية

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

نظائر الهيليوم مقياس لاكتشاف رواسب الذهب.. كيف ذلك؟

الصين تطلق أول ناقلة نفط خام ذكية في العالم تعمل بالميثانول

الزمن على المريخ أسرع من الأرض.. دراسة علمية تكشف الفوارق

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength