المرجع الالكتروني للمعلوماتية
المرجع الألكتروني للمعلوماتية

الرياضيات
عدد المواضيع في هذا القسم 9761 موضوعاً
تاريخ الرياضيات
الرياضيات المتقطعة
الجبر
الهندسة
المعادلات التفاضلية و التكاملية
التحليل
علماء الرياضيات

Untitled Document
أبحث عن شيء أخر
شروط الزكاة وما تجب فيه
2024-11-06
آفاق المستقبل في ضوء التحديات
2024-11-06
الروايات الفقهيّة من كتاب علي (عليه السلام) / حرمة الربا.
2024-11-06
تربية الماشية في ألمانيا
2024-11-06
أنواع الشهادة
2024-11-06
كيفية تقسم الخمس
2024-11-06

اعتراف الصحابة بقصور الكتاب والسنة
28-01-2015
context (n.)
2023-07-22
Euler Number Prime
22-9-2020
التحليل الجنائي لمخلفات الحرائق الجنائية
2023-12-06
Edge Automorphism Group
8-4-2022
Chromatically Equivalent Graphs
24-3-2022

Graphs  
  
1367   02:37 صباحاً   date: 23-2-2016
Author : Tony Crilly
Book or Source : 50 mathematical ideas you really need to know
Page and Part : 170-175


Read More
Date: 23-2-2016 1176
Date: 17-2-2016 1196
Date: 20-2-2016 1300

There are two types of graphs in mathematics. At school we draw curves which show the relationship between variables x and y. In the other more recent sort, dots are joined up by wiggly lines.

Königsberg is a city in East Prussia famous for the seven bridges which cross the River Pregel. Home to the illustrious philosopher Immanuel Kant, the city and its bridges are also linked with the famous mathematician Leonhard Euler.

In the 18th century a curious question was posed: was it possible to set off and walk around Königsberg crossing each bridge exactly once? The walk does not require us to finish where we started – only that we cross each bridge once.

In 1735, Euler presented his solution to the Russian Academy, a solution which is now seen as the beginning of modern graph theory. In our semi-abstract diagram, the island in the middle of the river is labelled I and the banks of the river by A, B and C. Can you plan a walk for a Sunday afternoon that crosses each bridge just once? Pick up a pencil and try it. The key step is to peel away the semi-abstractness and progress to complete abstraction. In so doing a graph of points and lines is obtained. The land is represented by ‘points’ and the bridges joining them are represented by ‘lines’. We don’t care that the lines are not straight or that they differ in length. These things are unimportant. It is only the connections that matter.

Euler made an observation about a successful walk. Apart from the beginning and the end of the walk, every time a bridge is crossed onto a piece of land it must be possible to leave it on a bridge not previously walked over.

Translating this thought into the abstract picture, we may say that lines meeting at a point must occur in pairs. Apart from two points representing the start and finish of the walk, the bridges can be traversed if and only if each point has an even number of lines incident on it.

The number of lines meeting at a point is called the ‘degree’ of the point.

Euler’s theorem states that

The bridges of a town or city may be traversed exactly once if, apart from at most two, all points have even degree.

Looking at the graph representing Königsberg, every point is of odd degree. This means that a walk crossing each bridge only once is not possible in Königsberg. If the bridge setup were changed then such a walk may become possible. If an extra bridge were built between the island I and C the degrees at I and C would both be even. This means we could begin a walk on A and end on B having walked over every bridge exactly once. If yet another bridge were built, this time between A and B (shown right), we could start anywhere and finish at the same place because every point would have even degree in this case.

The hand-shaking theorem

If we were asked to draw a graph that contained three points of odd degree, we would have a problem. Try it. It cannot be done because

In any graph the number of points with odd degree must be an even number.

This is the hand-shaking theorem – the first theorem of graph theory. In any graph every line has a beginning and an end, or in other words it takes two people to shake hands. If we add up the degrees of every point for the whole graph we must get an even number, say N. Next we say there are x points with odd degree and y points with even degree. Adding all the degrees of the odd points together we’ll have Nx and adding all the degrees of the even points will give us Ny, which is even. So we have Nx + Ny = N, and therefore Nx = NNy. It follows that Nx is even. But x itself cannot be odd because the addition of an odd number of odd degrees would be an odd number. So it follows that x must be even.

Non-planar graphs

The utilities problem is an old puzzle. Imagine three houses and three utilities – gas, electricity and water. We have to connect each of the houses to each of the utilities, but there’s a catch – the connections must not cross.

In fact this cannot be done – but you might try it out on your unsuspecting friends. The graph described by connecting three points to another three points in all possible ways (with only nine lines) cannot be drawn in the plane without crossings. Such a graph is called non-planar. This utilities graph, along with the graph made by all lines connecting five points, has a special place in graph theory. In 1930, the Polish mathematician Kazimierz Kuratowski proved the startling theorem that a graph is planar if and only if it does not contain either one of these two as a subgraph, a smaller graph contained within the main one.

Trees

A ‘tree’ is a particular kind of graph, very different from the utitlities graph or the Königsberg graph. In the Königsberg bridge problem there were opportunities for starting at a point and returning to it via a different route. Such a route from a point and back to itself is called a cycle. A tree is a graph which has no cycles.

A familiar example of a tree graph is the way directories are arranged in computers. They are arranged in a hierarchy with a root directory and subdirectories leading off it. Because there are no cycles there is no way to cross from one branch other than through the root directory – a familiar manoeuvre for computer users.

Counting trees

How many different trees can be made from a specific number of points? The problem of counting trees was tackled by the 19th-century English mathematician Arthur Cayley. For example, there are exactly three different tree types with five points:

Cayley was able to count the number of different tree types for small numbers of points. He was able to go as far as trees with fewer than 14 points before the sheer computational complexity was too much for a man without a computer. Since then the calculations have advanced as far as trees with as many as 22 points. There are millions of possible types for these.

Even in its own time, Cayley’s research had practical applications. Counting trees is relevant in chemistry, where the distinctiveness of some compounds depends on the way atoms are arranged in their molecules. Compounds with the same number of atoms but with different arrangements have different chemical properties. Using his analysis it was possible to predict the existence of chemicals ‘at the tip of his pen’ that were subsequently found in the laboratory.

the condensed idea

Across the bridges and into the trees

 

 




الجبر أحد الفروع الرئيسية في الرياضيات، حيث إن التمكن من الرياضيات يعتمد على الفهم السليم للجبر. ويستخدم المهندسون والعلماء الجبر يومياً، وتعول المشاريع التجارية والصناعية على الجبر لحل الكثير من المعضلات التي تتعرض لها. ونظراً لأهمية الجبر في الحياة العصرية فإنه يدرّس في المدارس والجامعات في جميع أنحاء العالم. ويُعجب الكثير من الدارسين للجبر بقدرته وفائدته الكبيرتين، إذ باستخدام الجبر يمكن للمرء أن يحل كثيرًا من المسائل التي يتعذر حلها باستخدام الحساب فقط.وجاء اسمه من كتاب عالم الرياضيات والفلك والرحالة محمد بن موسى الخورازمي.


يعتبر علم المثلثات Trigonometry علماً عربياً ، فرياضيو العرب فضلوا علم المثلثات عن علم الفلك كأنهما علمين متداخلين ، ونظموه تنظيماً فيه لكثير من الدقة ، وقد كان اليونان يستعملون وتر CORDE ضعف القوسي قياس الزوايا ، فاستعاض رياضيو العرب عن الوتر بالجيب SINUS فأنت هذه الاستعاضة إلى تسهيل كثير من الاعمال الرياضية.

تعتبر المعادلات التفاضلية خير وسيلة لوصف معظم المـسائل الهندسـية والرياضـية والعلمية على حد سواء، إذ يتضح ذلك جليا في وصف عمليات انتقال الحرارة، جريان الموائـع، الحركة الموجية، الدوائر الإلكترونية فضلاً عن استخدامها في مسائل الهياكل الإنشائية والوصف الرياضي للتفاعلات الكيميائية.
ففي في الرياضيات, يطلق اسم المعادلات التفاضلية على المعادلات التي تحوي مشتقات و تفاضلات لبعض الدوال الرياضية و تظهر فيها بشكل متغيرات المعادلة . و يكون الهدف من حل هذه المعادلات هو إيجاد هذه الدوال الرياضية التي تحقق مشتقات هذه المعادلات.