pranshul24.github.io/greedy_graph.html at master · pranshul24/pranshul24.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
<!DOCTYPE html>
<html lang="en">

<head>
    <!-- Required meta tags always come first -->
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    <meta http-equiv="x-ua-compatible" content="ie=edge">

    <!-- Bootstrap CSS -->
    <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
    <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3.0.1/es5/tex-mml-chtml.js"></script>
    <script src="https://use.fontawesome.com/8ca8c8dba3.js"></script>
    <link href='https://fonts.googleapis.com/css?family=Actor' rel='stylesheet'>
    <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.5.0/css/bootstrap.min.css"
        integrity="sha384-9aIt2nRpC12Uk9gS9baDl411NQApFmC26EwAOH8WgZl5MYYxFfc+NcPb1dKGj7Sk" crossorigin="anonymous">
    <link rel="stylesheet" href="css/styles.css">
    <script src="jquery-3.5.1.min.js"></script>
    <link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.3.2/styles/default.min.css">
    <script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.3.2/highlight.min.js"></script>
    <title>Algotricks</title>
</head>

<body style="background-color:#5a707a;">
    <nav class=" navbar navbar-dark navbar-expand-sm fixed-top">
        <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#Navbar">
            <span class="navbar-toggler-icon"></span>
        </button>
        <a class="navbar-brand mr-auto ml-3" href="./index.html"><b>Algotricks</b></a>
        <div class="collapse navbar-collapse" id="Navbar">
            <ul class="navbar-nav mr-auto">
                <li class="nav-item"><a class="nav-link" href="index.html"><span class="fa fa-home fa-lg"></span>
                        Home</a></li>
                <li class="nav-item active"><a class="nav-link" href="menu.html"><span class="fa fa-list fa-lg"></span>
                        List</a>
                </li>
            </ul>
        </div>
    </nav>
    <div class="container" style="border-bottom: 1px ridge;">
        <br>
        <div class="row row-content align-items-center">
            <div class="col-12 align-self-center">
                <div class="text-center">
                    <img src="img/ques_greedy2.png">
                </div>
            </div>
        </div>
        <br>
        <div class="row row-content align-items-center">
            <div class="col-4 align-self-center">
                <div class="text-center">
                    <img src="img/greedy2/1.svg">
                </div>
            </div>
            <div class="col-4 align-self-center">
                <div class="text-center">
                    <img src="img/greedy2/2.svg">
                </div>
            </div>
            <div class="col-4 align-self-center">
                <div class="text-center">
                    <img src="img/greedy2/3.svg">
                </div>
            </div>
        </div>
        <br>
        <div class="row row-content align-items-center">
            <div class="col-12 align-self-center">
                <div class="text-center">
                    <img src="img/greedy2.png">
                </div>
            </div>
        </div>
        <br>
        <div class="row row-content align-items-center">
            <div class="col-12 align-self-center">
                <div class="text-center">
                    <div class="card text-white bg-dark">
                        <div class="card-header">
                            <h3>Solution</h3>
                        </div>
                        <div class="card-body">
                            <p class="card-text">
                                Let say a node is of degree d , then to color this node and all its adjacent nodes we
                                need (d+1) distinct colors . For example let us take d=4 then as shown in image above
                                :<br>
                                1st : nodes 1,2 and 3 have to be of different colors<br>
                                2nd : now 4 should be of different color from nodes 1,2 and 2,3 , therefore it is
                                colored different from 1,2,3<br>
                                3rd : now 5 should be of different color from nodes 2,1 and 2,3 and 2,4 , therefore it
                                is colored different from 1,2,3,4<br>
                                Hence therfore we need atleast D+1 colors , where D is maximum degree of a node in the
                                tree , but we can prove that we don't require more than D+1 colors : Let us root tree at
                                any node . Now for any node its color , its parent color and the color of all its
                                children
                                should be different as explained already . Now for the child's children we have ( D+1-2
                                ) colors (excluding child and parent's color) so we can color them even if the degree is
                                D (so maximum D-1 children we have to color). Hence we can say greedily that we can
                                always color the tree with D+1 colors.
                                Now to find 1 such coloring we can use dfs where we store color of each node . We send
                                the parent also in dfs so as to not color the children with the color of the parent and
                                itself .
                            <div class=""></div>
                            </p>
                        </div>
                    </div>

                </div>
            </div>
        </div><br>
        <div class="row row-content align-items-center">
            <div class="col-12 align-self-center">
                <div class="text-center">
                    <img src="img/greedy2_animation/loopingImage.gif">
                </div>
            </div>
        </div>
        <hr style="height:2px;border-width:0;color:white;background-color:white">
        <br>
        <div class="row row-content align-items-center">
            <div class="col-12 align-self-center">
                <div class="text-center">
                    <img src="img/prob3/prob.png" width="900px">
                </div>
            </div>
        </div><br>
        <div class="row row-content align-items-center">
            <div class="col-6 align-self-center">
                <div class="text-center">
                    <img src="img/prob3/loopingImage.gif">
                </div>
            </div>
            <div class="col-6 align-self-center">
                <div class="text-center">
                    <img src="img/prob3_2/loopingImage.gif">
                </div>
            </div>
        </div>
        <br><br>
        <div class="row row-content align-items-center">
            <div class="col-12 align-self-center">
                <div class="text-center">
                    <img src="img/prob3/sol.png" width="900px">
                </div>
            </div>
        </div><br>
        <div class="row row-content align-items-center">
            <div class="col-12 align-self-center">
                <div class="text-center">
                    <img src="img/prob3/Slide31.jpg" width="900px">
                </div>
            </div>
        </div><br>
        <hr style="height:2px;border-width:0;color:white;background-color:white">
        <br>
    </div>
    <footer class="footer">
        <div class="container">
            <div class="row">
                <div class="col-12 align-self-center">
                    <div class="text-center">
                        <h6 style="color: #eceff1;font-size:30px;">You can contact me here ...</h6>
                    </div>
                </div>
            </div>
            <div class="row">
                <div class="col-12 align-self-center">
                    <div class="text-center">
                        <a class="btn btn-social-icon btn-facebook" href="https://www.facebook.com/pranshul.chawla"><i
                                class="fa fa-facebook fa-2x"></i></a>
                        <a class="btn btn-social-icon btn-instagram" href="https://www.instagram.com/pranshulchawla/"><i
                                class="fa fa-instagram fa-2x"></i></a>
                    </div>
                </div>
            </div>
        </div>
    </footer>
</body>

</html>